觉得这道题以后可以和优先队列结合起来 嗯
就是说依次去掉前n条路求连通块数量
处理的时候 只要每次merge发现父亲不相等 然后进到里面合并的时候 num--
wa了好几次是因为最后输出的时候开了点的数量大小的数组而不是操作数量数组 orz
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65535/65535 K (Java/Others)
Total Submission(s): 5334 Accepted Submission(s): 1864
#include<iostream> #include<cmath> #include<cstdio> #include<cstring> using namespace std; const int MAXN = 10000; const int MAXM = 100000; int father[MAXN + 100]; int u[MAXM + 100]; int v[MAXM + 100]; int ans[MAXM + 100]; int n,m,num; void initt(){ for(int i = 0;i < n;i++){ father[i] = i; } return; } int findd(int u){ if(father[u] == u) return father[u]; father[u] = findd(father[u]); return father[u]; } void mergee(int u,int v){ int fatu = findd(u); int fatv = findd(v); if(fatu != fatv){ num--; father[fatu] = fatv; } } int main(){ while(~scanf("%d%d",&n,&m)){ //initt(); for(int i = 0;i < n;i++){ father[i] = i; } for(int i = 0;i < m;i++){ scanf("%d%d",u+i,v+i); } num = n; for(int i = m-1;i >= 1;i--){ mergee(u[i],v[i]); ans[i] = num; } ans[m] = n; for(int i = 1;i <= m;i++){ printf("%d\n",ans[i]); } } return 0; }
原文:https://www.cnblogs.com/xuyanqd/p/9028854.html