学步园

算法分类：

数据结构

算法原理：

通过find函数找出该节点的根节点，

通过UNION函数将两棵树合并。

加入rank[N]来记录每个节点的秩（即树的高度），并按秩进行合并，可避免合并时的最糟糕情况，（树形为一条直线）

通过路径压缩可以减少每次寻找根节点的次数。

算法时间复杂度：

最坏情况为O（mlogn）

一般为O（m）

代码实现：（HDU1232-畅通工程）

/*
 * HDU 1232 畅通工程
 * 并查集
 */ 
#include <iostream>
using namespace std;

const int SIZE = 1005;
int root[SIZE];
int rank[SIZE];

int find(int x) {
	int y = x;
	while (root[y] != y) {
		y = root[y];	
	}
	
	int temp, head = y;
	y = x;
	while (root[y] != y) {
		temp = root[y];
		root[y] = head;
		y = temp;	
	}
	
	return head;
};

void UNION(int x, int y) {
	int f1 = find(x);
	int f2 = find(y);
	
	if (rank[f1] <= rank[f2]) {
		root[f1] = f2;
		if (rank[f1] == rank[f2]) {
			rank[f2] ++; 	
		}	
	} else {
		root[f2] = f1;
	}
};

int main()
{
	int N, M, s, e, count;
	
	while (scanf("%d%d",&N,&M)!=EOF, N) {
		for (int i = 1; i <= N; ++ i) 
			root[i] = i;
		
		for (int i = 0; i < M; ++ i) {
			scanf("%d%d",&s,&e);
			UNION(s,e);
		}
		
		count = -1;
		for (int i = 1; i <= N; ++ i) {
			if (root[i] == i) 
				++ count;
		}
		
		printf("%d\n",count);
	}
}