题目:
题意：
给了一个联通无向图，现在问去掉某个点，会让图变成几个联通块?
输出的按分出的从多到小，若相等，输出标号从小到大。输出M个。
分析：
BCC求割点后联通块数量，Tarjan算法。
联通块的数目在找到一个low[y]>=dfn[x]时累加，最后加一即可。
代码如下：
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cstring> 4 #include<iostream> 5 #include<algorithm> 6 using namespace std; 7 #define Maxn 10010 8 9 int n,m; 10 int first[Maxn],low[Maxn],dfn[Maxn],fa[Maxn],son[Maxn]; 11 int cut[Maxn]; 12 int cnt; 13 14 struct node 15 { 16 int x,y,next; 17 }; 18 node t[Maxn*10],ans[Maxn]; 19 int len; 20 21 int mymin(int x,int y) {return x<y?x:y;} 22 23 void ins(int x,int y) 24 { 25 t[++len].x=x;t[len].y=y; 26 t[len].next=first[x];first[x]=len; 27 } 28 29 bool cmp(node x,node y) {return (x.x==y.x)?(x.y<y.y):(x.x>y.x);} 30 31 void ffind(int x,int f) 32 { 33 dfn[x]=low[x]=++cnt; 34 fa[x]=f; 35 for(int i=first[x];i;i=t[i].next) if(t[i].y!=f) 36 { 37 int y=t[i].y; 38 if(dfn[y]==0) 39 { 40 ffind(y,x); 41 son[x]++; 42 low[x]=mymin(low[x],low[y]); 43 if(low[y]>=dfn[x]) cut[x]++; 44 } 45 else low[x]=mymin(low[x],dfn[y]); 46 } 47 } 48 49 int main() 50 { 51 while(1) 52 { 53 scanf("%d%d",&n,&m); 54 if(n==0&&m==0) break; 55 len=0;cnt=0; 56 memset(first,0,sizeof(first)); 57 while(1) 58 { 59 int a,b; 60 scanf("%d%d",&a,&b); 61 if(a==-1&&b==-1) break; 62 a++;b++; 63 ins(a,b);ins(b,a); 64 } 65 memset(dfn,0,sizeof(dfn)); 66 memset(cut,0,sizeof(cut)); 67 memset(son,0,sizeof(son)); 68 ffind(1,0);ans[1].y=0; 69 if(son[1]>1) ans[1].x=son[1]; 70 else ans[1].x=1; 71 for(int i=2;i<=n;i++) 72 { 73 ans[i].y=i-1; 74 ans[i].x=cut[i]+1; 75 } 76 sort(ans+1,ans+1+n,cmp); 77 for(int i=1;i<=m;i++) printf("%d %d\n",ans[i].y,ans[i].x); 78 printf("\n"); 79 } 80 return 0; 81 }
2016-03-17 13:43:40