这题是并查集的应用 .
如果看出来怎么解答确实很快.套模板就可以了.
可惜自己太菜,没想出来.
比赛的时候想到要反向,不过事实证明还是思路错了.
做的题目太少的缘故,多做点题目,多见见世面.
题目的意思大概是每次删除一些边,然后问你有多少块.明显的并查集.
可以通过反向建图,就是对所有的状态取反,所以要从最后一条边开始建图.
感谢 http://blog.csdn.net/acmmmm/article/details/10820117 九野的博客 点明了想法.
1 #include<algorithm> 2 #include<iostream> 3 #include<math.h> 4 #define N 10001 5 #define M 100050 6 using namespace std; 7 int father[N]; 8 int find(int x){ 9 if(x!=father[x]) 10 father[x]=find(father[x]); 11 return father[x]; 12 } 13 int ans[M],s[M],t[M]; 14 int main(){ 15 int n,m,i; 16 while(~scanf("%d%d",&n,&m)) 17 { 18 for(i=0;i<=n;i++) father[i]=i; 19 for(i=1;i<=m;i++) 20 scanf("%d%d",&s[i],&t[i]); 21 ans[m]=n; 22 for(i=m;i>1;i--) 23 { 24 int a=find(s[i]),b=find(t[i]); 25 if(find(a)!=find(b)) 26 { 27 father[a]=b; 28 ans[i-1]=ans[i]-1; 29 } 30 else ans[i-1]=ans[i]; 31 } 32 for(i=1;i<=m;i++) 33 printf("%d ",ans[i]); 34 } 35 return 0; 36 }