CSUOJ 1601 War (離線並查集求連通塊個數)

CSUOJ 1601 War (離線並查集求連通塊個數)

Description

AME decided to destroy CH’s country. In CH’ country, There are N villages, which are numbered from 1 to N. We say two village A and B are connected, if and only if there is a road between A and B, or there exists a village C such that there is a road between A and C, and C and B are connected. To defend the country from the attack of AME, CH has decided to build some roads between some villages. Let us say that two villages belong to the same garrison area if they are connected.
Now AME has already worked out the overall plan including which road and in which order would be attacked and destroyed. CH wants to know the number of garrison areas in his country after each of AME’s attack.

Input

The first line contains two integers N and M — the number of villages and roads, (2 ≤ N ≤ 100000; 1 ≤ M ≤ 100000). Each of the next M lines contains two different integers u, v (1<=u, v<=N)—which means there is a road between u and v. The next line contains an integer Q which denotes the quantity of roads AME wants to destroy (1 ≤ Q ≤ M). The last line contains a series of numbers each of which denoting a road as its order of appearance — different integers separated by spaces.

Output

Output Q integers — the number of garrison areas in CH’s country after each of AME's attack. Each pair of numbers are separated by a single space.

Sample Input

3 1
1 2
1
1
4 4
1 2
2 3
1 3
3 4
3
2 4 3

Sample Output

3
1 2 3

題目鏈接：http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1601

題目大意：n個點m條邊（邊1，邊2...邊m），q個要摧毀的邊，求按順序每摧毀一條邊後圖中連通塊的個數

題目分析：離線並查集，反向加邊，先將q條路全部摧毀後的連通塊個數求出來，然後加邊即可，每加一條邊，若兩點不在同一連通塊中，則合並且連通塊個數減1

#include 
#include 
int const MAX = 1e5 + 5;
int fa[MAX], n, m;
int x[MAX], y[MAX], r[MAX];
int ans, res[MAX];
bool vis[MAX];

void UF_set()
{
	for(int i = 0; i <= n; i++)
		fa[i] = i;
}

int Find(int x)
{
	return x == fa[x] ? x : fa[x] = Find(fa[x]);
}

void Union(int a, int b)
{
	int r1 = Find(a);
	int r2 = Find(b);
	if(r1 != r2)
	{
		fa[r2] = r1;
		ans --;
	}
}

int main()
{
	while(scanf("%d %d", &n, &m) != EOF)
	{
		UF_set();
		ans = n;
		memset(vis, false, sizeof(vis));
		for(int i = 1; i <= m; i++)
			scanf("%d %d", &x[i], &y[i]);
		int q;
		scanf("%d", &q);
		for(int i = 1; i <= q; i++)
		{
			scanf("%d", &r[i]);
			vis[r[i]] = true;
		}
		for(int i = 1; i <= m; i++)
			if(!vis[i])
				Union(x[i], y[i]);
		for(int i = q; i >= 1; i--)
		{
			res[i] = ans;
			Union(x[r[i]], y[r[i]]);	
		}
		for(int i = 1; i < q; i++)
			printf("%d ", res[i]);
		printf("%d\n", res[q]);
	}
}