【并查集】hdu4496
D-City
Problem Description
Luxer is a really bad guy. He destroys everything he met.
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.
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.
Input
First line of the input contains two integers N and M.
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.
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.
Output
Output M lines, the ith line is the answer after deleting the first i edges in the input.
Sample Input
5 10 0 1 1 2 1 3 1 4 0 2 2 3 0 4 0 3 3 4 2 4
Sample Output
1 1 1 2 2 2 2 3 4 5
Hint
The graph given in sample input is a complete graph, that each pair of vertex has an edge connecting them, so there's only 1 connected block at first. The first 3 lines of output are 1s because after deleting the first 3 edges of the graph, all vertexes still connected together. But after deleting the first 4 edges of the graph, vertex 1 will be disconnected with other vertex, and it became an independent connected block. Continue deleting edges the disconnected blocks increased and f vertex, so the last output should always be N. 一条一条边的删除是不科学的，但是可以倒过来——从最后一条边开始把每条边一一加入到图中，如果该条边是在某两个联通块之间就说明联通块的个数会在此之后减少1，否则个数不变（一条边都没加的时候联通块数等于点的数目），然后再反向输出就好了！这个显然是用并查集实现！
注意点是从零开始的（我最开始数组清零的时候是从1开始的（读题不认真啊 
，没有观察数据啊 ），囧……）
，没有观察数据啊 ），囧……） #include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
long t;
long n, m;
long f[10010];
long re[100100], a[100100], b[100100];
long find(long x)
{
if (f[x] == x) return x;
f[x] = find(f[x]);
return(f[x]);
}
void merge(long x, long y)
{
x = find(f[x]);
f[x] = find (y);
}
int main()
{
//freopen("D.in", "r", stdin);
while(scanf("%d%d", &n, &m) == 2)
{
for (long i=1; i<=m; i++)
{
scanf("%d%d", &a[i], &b[i]);
}
for (long i = 0; i <= n-1; i++)
f[i]=i;
re[m]=n;
for(long i = m; i >= 1; i--)
{
if (find(a[i]) != find(b[i]))
{
re[i-1] = re[i] -1;
merge(a[i], b[i]);
}
else re[i-1] = re[i];
}
for(long i=1; i<=m; i++)
{
printf("%d\n",re[i]);
}
}
return 0;
}
投递牛客等公司10个岗位 >
快手公司福利 222人发布
