Uva(10765)(Doves and bombs)

链接：https://vjudge.net/problem/UVA-10765
思路：本质上还是个求双连通分量的问题，因为是点双，所以每个割点所属的双连通分量是不确定的，如何判断缩点后一个点周围的双连通分量个数就成了一直卡住我的问题，后来发现其实特别简单，只需要在tarjan算法弹出双连通分量是用一个数组每次+1即可！！！！，因为每次求出新连通块是在割点的基础上做的tarjan算法。砍点后的连通块个数分情况讨论：若为割点则为他周围不同的双连通分量的个数，若不为割点则还是为一个连通块。
代码：

 #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;
}