王道并查集代码

int find(int s[], int x) {
	int root = x;
	// 先找出根节点 
	while (s[x] >= 0) root = s[root];
	// return root;
	while (s[x] >= 0) {
		// 如果不是则将节点接到根节点上
		int tmp = s[x]; 
		s[x] = root;
		x = s[x];
	}
	return root;
}

void union(int s[], int root1, int root2) {
	if (root1 == root2) return ;
	// 都是负数 roo2小 所以 root2节点数更多 
	if (s[root1] > s[root2]) {
		s[root2] += s[root1];
		s[root1] = root1;
	} else {
		s[root1] += s[root2];
		s[root2] = root1;
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26