UVA 10765 Doves and bombs（双连通分量）

题意：在一个无向连通图上，求任意删除一个点，余下连通块的个数。

对于一个非割顶的点，删除之后，原图仍连通，即余下连通块个数为1；对于割顶，余下连通块个数>=2。

由于是用dfs查找双连通分量，树形结构是向下搜素，所以在dfs过程中不便于统计割顶所分连通分量的个数。换一个角度，通过在vector<int>bcc中保存各个双连通分量的点，统计各个点出现的次数即可。（除割顶外，每个点只可能出现一次）

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<algorithm>
  4 #include<vector>
  5 #include<stack>
  6 using namespace std;
  7 
  8 const int MAXN= 11111;
  9 
 10 struct Edge{
 11     int u,v;
 12     Edge(){}
 13     Edge(int _u,int _v):u(_u),v(_v){}
 14 };
 15 
 16 struct Cut{
 17     int c,w;
 18 }cut[MAXN];
 19 
 20 int iscut[MAXN],pre[MAXN],low[MAXN],dfs_clock,bcc_cnt,bccno[MAXN];
 21 int son;
 22 vector<int >G[MAXN],bcc[MAXN];
 23 stack<Edge>stk;
 24 
 25 void dfs(int u,int fa)
 26 {
 27     pre[u]=low[u]=dfs_clock++;
 28     son=0;
 29     for(int i=0;i<G[u].size();i++)
 30     {
 31         int v=G[u][i];
 32         Edge e=Edge(u,v);
 33         if(!pre[v]){
 34             stk.push(e);
 35             son++;
 36             dfs(v,u);
 37             low[u]=min(low[u],low[v]);
 38             if(low[v]>=pre[u]){
 39                 iscut[u]=1;
 40                 bcc_cnt++;
 41                 bcc[bcc_cnt].clear();
 42                 while(1)
 43                 {
 44                     Edge x=stk.top();
 45                     stk.pop();
 46                     if(bccno[x.u]!=bcc_cnt){
 47                         bcc[bcc_cnt].push_back(x.u);
 48                         bccno[x.u]=bcc_cnt;
 49                     }
 50                     if(bccno[x.v]!=bcc_cnt){
 51                         bcc[bcc_cnt].push_back(x.v);
 52                         bccno[x.v]=bcc_cnt;
 53                     }
 54                     if(x.u==u&&x.v==v)
 55                         break;
 56                 }
 57             }
 58         }else if(pre[v]<pre[u]&&v!=fa){
 59             stk.push(e);
 60             low[u]=min(low[u],pre[v]);
 61         }
 62     }
 63     if(fa==-1&&son==1)
 64         iscut[u]=0;
 65 }
 66 
 67 void find_bcc(int n)
 68 {
 69     bcc_cnt=dfs_clock=0;
 70     memset(pre,0,sizeof(pre));
 71     memset(bccno,0,sizeof(bccno));
 72     memset(iscut,0,sizeof(iscut));
 73     memset(cut,0,sizeof(cut));
 74 
 75     for(int i=0;i<n;i++)
 76         if(!pre[i])
 77             dfs(i,-1);
 78 }
 79 
 80 int cmp(Cut a,Cut b)
 81 {
 82     if(a.w==b.w)
 83         return a.c<b.c;
 84     return a.w>b.w;
 85 }
 86 
 87 int main()
 88 {
 89     int n,m,x,y;
 90     while(~scanf("%d%d",&n,&m))
 91     {
 92         if(!n&&!m)
 93             return 0;
 94         for(int i=0;i<n;i++)
 95             G[i].clear();
 96 
 97         while(1)
 98         {
 99             scanf("%d%d",&x,&y);
100             if(x==-1&&y==-1)
101                 break;
102             G[x].push_back(y);
103             G[y].push_back(x);
104         }
105 
106         find_bcc(n);
107 
108         for(int i=1;i<=bcc_cnt;i++)
109         {
110             for(int j=0;j<bcc[i].size();j++)
111             {
112                 cut[bcc[i][j]].c=bcc[i][j];
113                 cut[bcc[i][j]].w++;
114             }
115         }
116         sort(cut,cut+n,cmp);
117         for(int i=0;i<m;i++)
118             printf("%d %d
",cut[i].c,cut[i].w);
119         puts("");
120     }
121     return 0;
122 }

View Code