从后面到前面,把破坏桥看成建立桥,之后连通的集合个数反序输出就可以了
#include<stdio.h> #include<string.h> #include<ctype.h> #include<stdlib.h> #include<math.h> #define maxn 100010 int n,m; int fa[maxn],v[maxn],u[maxn],res[maxn]; int find(int x) { return fa[x]==x?x:(fa[x]=find(fa[x])); } main() { int i,num,a,b; //freopen("D:\\in.txt","r",stdin); while(scanf("%d%d",&n,&m)!=EOF) { res[0]=num=n; for(i=0;i<n;i++) fa[i]=i; for(i=0;i<m;i++) scanf("%d%d",&u[i],&v[i]); for(i=m-1;i>=0;i--) { a=find(u[i]); b=find(v[i]); if(a!=b) { fa[a]=b; num--; } res[m-i]=num; } for(i=m-1;i>=0;i--) printf("%d\n",res[i]); } return 0; }