并查集,即不相交集合,用森林表示。主要操作有初始化、查询、合并。

初始化

每个元素都建立一个只含自己的集合,每个元素都是自己所在集合的代表,把每个元素的父结点设为自己。

查询

一个元素所在有根树的根结点,就是这个集合的代表元素。

合并

合并两个元素所在的集合,首先找到这两个集合的代表元素,然后其中一个作为另一个的父亲就可以了。

按秩合并优化

每次合并时都尽可能让合并后有根树的最大深度不要过深,从而避免出现类似一条链的情况发生。 秩是指结点高度的上界,在按秩合并中,具有较小的秩的根在合并时要指向具有较大秩的根。 用数组 rank 存储每个结点的秩,在合并时判断秩的大小来决定谁作为根结点。

路径压缩优化

查找的时候,路径压缩优化会将从 a 到 d 路径上所有点都指向有根树的根。这样有根树的高度可以尽可能的降低,下次再操作就更省时了。

#include <iostream>
using namespace std;
 
class DisjointSet {
private:
	int *father, *rank;
public:
	DisjointSet(int size) {
		//初始化
		father = new int[size];
		rank = new int[size];
		for (int i = 0; i < size; ++i) {
			father[i] = i;
			rank[i] = 0;
		}
	}
	~DisjointSet() {
		delete[] father;
		delete[] rank;
	}
	//查询
	int find_set(int node) {
		if (father[node] != node) {
			father[node] = find_set(father[node]);
		}
		return father[node];
	}
	//合并
	bool merge(int node1, int node2) {
		int ancestor1 = find_set(node1);
		int ancestor2 = find_set(node2);
		if (ancestor1 != ancestor2) {
			if (rank[ancestor1] > rank[ancestor2]) {
				swap(ancestor1, ancestor2);
			}
			father[ancestor1] = ancestor2;
			rank[ancestor2] = max(rank[ancestor1] + 1, rank[ancestor2]);
			return true;
		}
		return false;
	}
};
 
int main() {
	DisjointSet dsu(100);
	int m, x, y;
	cin >> m;
	for (int i = 0; i < m; ++i) {
		cin >> x >> y;
		bool ans = dsu.merge(x, y);
		if (ans) {
			cout << "success" << endl;
		}
		else {
			cout << "failed" << endl;
		}
	}
	return 0;
}

在数据结构里,森林是由若干棵互不相交的树组成的。

森林有两种遍历方法,分别是先序遍历和后序遍历。请注意,森林是没有和树的中序遍历对应的遍历方法的。

因为中序遍历只存在于二叉树中,而森林中的树都是一般树,无法区分左右孩子,自然也就无法进行中序遍历了。