UVa 10583 Ubiquitous Religions

做disjoint set，架構與UVa 793 Network Connections一樣。

	#include <cstdio>
	#include <set>
	using namespace std;
	int Set[50010];
	int nOfReligion;
	void Set_Initial(int N);
	int FindRoot(int x);
	void Union(int x, int y);
	int main()
	{
	int N, M, Case = 1;
	while (scanf("%d %d", &N, &M) && (N || M)) {
	Set_Initial(N);
	int x, y;
	nOfReligion = N;
	while (M--) {
	scanf("%d%d", &x, &y);
	Union(x, y);
	}
	printf("Case %d: %d\n", Case++, nOfReligion);
	}
	return 0;
	}
	void Set_Initial(int N)
	{
	for (int i = 1; i <= N; ++i)
	Set[i] = i;
	}
	int FindRoot(int x)
	{
	if (x == Set[x])
	return x;
	return Set[x] = FindRoot(Set[x]);
	}
	void Union(int x, int y)
	{
	x = FindRoot(x);
	y = FindRoot(y);
	if (x != y) {
	Set[x] = y;
	--nOfReligion;
	}
	}

view raw [UVa] 10583 Ubiquitous Religions.cpp hosted with ❤ by GitHub