hdoj 1232 暢通工程 [並查集]

hdoj 1232 暢通工程 [並查集]

策略： 如題。

並查集：並查集是一種樹型的數據結構，用於處理一些不相交集合（Disjoint Sets）的合並及查詢問題。 說白了就是點的合並與查詢。

代碼：

#include
#include
int fat[1005];
int f(int n){
	if(fat[n] != n) fat[n] = f(fat[n]);
	else
	return fat[n];
}
int main()
{
	int n, m, i;
	while(scanf(%d, &n), n){
		scanf(%d, &m);
		for(i = 1; i <= n; i ++)
			fat[i] = i;
			int a, b;
		while(m --){
			scanf(%d%d, &a, &b);
			int x = f(a);
			int y = f(b);
			if(x != y){ //如果 a的祖先不等於b的祖先，就讓b的祖先的祖先等於a的祖先，這樣兩個集合就合並成了一個
				fat[y] = x;
			}
		}
		int ans = 0;
		for(i = 1; i <= n; i ++)
			if(fat[i] == i)
			++ans;
		printf(%d
, ans-1);
	}
	return 0;
}