并查集及其优化

1.并查集

#define SIZE 100
int UFSets[SIZE];

void Initial(int S[]) {
	for (int i = 0; i < SIZE; i++)
		S[i]=-1;
}

int Find(int S[], int x) {//查
	while(S[x] >= 0)
		x = S[x];
	return x;
}

void Union(int S[], int Root1, int Root2) {//并
	if(Root1 == Root2)
		return;
	S[Root2] = Root1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

Find操作最坏时间复杂度：O(n)
Union操作最坏时间复杂度：O(1)
优化Union操作，小树并入大树，减少Find操作的复杂度。

2.优化

void Union(int S[], int Root1, int Root2) {
	if(Root1 == Root2)
		return;
	if(Root2 > Root1) {
		S[Root1] += S[Root2];
		S[Root2] = Root1;
	}
	else {
		S[Root2] += S[Root1];
		S[Root1] = Root2;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12

Find操作最坏时间复杂度：O(logn)

2.进一步优化：压缩路径

优化Find操作，使树更矮。

int Find(int S[], int x) {
	int root = x;
	while(S[x] >= 0)
		root = S[root];
	while(x != root) {
		int t = S[x];
		S[x] = root;
		x = t;
	}
	return root;
}
1
2
3
4
5
6
7
8
9
10
11

Find操作最坏时间复杂度：O(α(n))