鏈接：https://vjudge.net/problem/UVA-10765
思路：本質上還是個求雙連通分量的問題，因為是點雙，所以每個割點所屬的雙連通分量是不確定的，如何判斷縮點后一個點周圍的雙連通分量個數(shù)就成了一直卡住我的問題，后來發(fā)現(xiàn)其實特別簡單，只需要在tarjan算法彈出雙連通分量是用一個數(shù)組每次+1即可?。。。?，因為每次求出新連通塊是在割點的基礎上做的tarjan算法?？滁c后的連通塊個數(shù)分情況討論：若為割點則為他周圍不同的雙連通分量的個數(shù)，若不為割點則還是為一個連通塊。
代碼：

 #include<cstdio>
#include<deque>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;


const int maxn = 10001;

struct sta{
    int id,num;
}res[maxn];

vector<int> G[maxn],bcc[maxn];
int iscut[maxn],io[maxn],dfn[maxn],low[maxn],bccno[maxn];
int n,m,ntime,bcc_cnt;

struct edge{
    int u,v;
    edge(){}
    edge(int uu,int vv):u(uu),v(vv){}
};

deque<edge> edges;

void tarjan(int u,int f){
    dfn[u] = low[u] = ++ntime;
    int child = 0;
    for(int i=0;i<G[u].size();i++){
        int v = G[u][i];
        if(!dfn[v]){
            child++;
            edges.push_back(edge(u,v));
            tarjan(v,u);
            low[u] = min(low[u],low[v]);
            if(dfn[u]<=low[v]){
                io[u]++;//只需在此處多一步更新即可！?。?                edge tmp;
                iscut[u] = 1;
                bcc_cnt++;
                bcc[bcc_cnt].clear();
                do{
                    tmp = edges.back();
                    edges.pop_back();
                    if(bccno[tmp.u]!=bcc_cnt){
                        bcc[bcc_cnt].push_back(tmp.u);
                        bccno[tmp.u] = bcc_cnt;
                    }
                    if(bccno[tmp.v]!=bcc_cnt){
                        bcc[bcc_cnt].push_back(tmp.v);
                        bccno[tmp.v] = bcc_cnt;
                    }
                }while(!(tmp.u==u&&tmp.v==v));
            }
        }
        else if(dfn[v]<dfn[u]&&v!=f){
            edges.push_back(edge(u,v));
            low[u] = min(low[u],dfn[v]);
        }
    }
    if(f<0&&child==1)iscut[u] = 0;
}

void find_bcc(int n){
    memset(dfn,0,sizeof(dfn));
    memset(iscut,0,sizeof(iscut));
    memset(bccno,0,sizeof(bccno));
    ntime = bcc_cnt = 0;
    for(int i=0;i<n;i++)if(!dfn[i])tarjan(i,-1);
}

bool cmp(const sta &q1,const sta &q2){
    return q1.num>q2.num||(q1.num==q2.num&&q1.id<q2.id);
}

int main(){
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    while(scanf("%d%d",&n,&m)&&(n||m)){
        for(int i=0;i<n;i++)G[i].clear();
        for(int i=0;i<n;i++)io[i]= 1;
        while(1){
          int a,b;
            scanf("%d%d",&a,&b);
            if(a<0||b<0)break;
            G[a].push_back(b);
            G[b].push_back(a);
        }
        find_bcc(n);
    
    for(int i=0;i<n;i++){
        res[i].id = i;
        if(!iscut[i])res[i].num = 1;
        else{
            res[i].num = io[i];
        } 
    }
    sort(res,res+n,cmp);
    for(int i=0;i<m;i++){
        printf("%d %d\n",res[i].id,res[i].num);
    }
  printf("\n");
    }
    return 0;
}