主题链接:http://acm.hdu.edu.cn/showproblem.php?pid=4496
D-City
One day Luxer went to D-city. D-city has N D-points and M D-lines. Each D-line connects exactly two D-points. Luxer will destroy all the D-lines. The mayor of D-city wants to know how many connected blocks of D-city left after Luxer destroying the first K D-lines in the input.
Two points are in the same connected blocks if and only if they connect to each other directly or indirectly.
Then following M lines each containing 2 space-separated integers u and v, which denotes an D-line.
Constraints:
0 < N <= 10000
0 < M <= 100000
0 <= u, v < N.
试试,生活亦是如此)。
向的时候去掉当中某条边的,独立的点不一定会增多(去掉这条边后还有
其它边间接的相连)。所以当我们逆向思考的时候,仅仅会在添加某一条边
时降低独立的点(也就是联通的点增多),这样仅仅会在他之后才会有可能
有某条边的操作是“无效”的(联通的点不变);
#include <cstdio> #include <cstring> const int maxn = 100017; int father[maxn]; int findd(int x) { //return x==father[x] ?
x : father[x]=findd(father[x]); if(father[x] == -1) { return x; } return father[x] = findd(father[x]); } int main() { int n, m; while(~scanf("%d%d",&n,&m)) { for(int i = 0; i < n; i++) { father[i] = -1; } int a[maxn], b[maxn], ans[maxn]; for(int i = 1; i <= m; i++) { scanf("%d%d",&a[i],&b[i]); } ans[m] = n; for(int i = m; i > 1; i--) { int u, v; //scanf("%d%d",&u,&v); int f1 = findd(a[i]); int f2 = findd(b[i]); //printf("f1:%d f2:%d\n",f1,f2); if(f1 != f2) { ans[i-1] = ans[i]-1; father[f1] = f2; } else { ans[i-1] = ans[i]; } } for(int i = 1; i <= m; i++) { printf("%d\n",ans[i]); } } return 0; }
版权声明:本文博客原创文章,博客,未经同意,不得转载。
本文转自mfrbuaa博客园博客,原文链接:http://www.cnblogs.com/mfrbuaa/p/4721741.html,如需转载请自行联系原作者