并查集(路径压缩)C++实现

代码语言：javascript复制

class UnionFind {
private:
	int *father;
	int count;
public:
	UnionFind(int n) {
		this->count = n;
		father = new int[n];
		for (int i=0; i<n;   i) father[i] = i;
	}
	~UnionFind(int n) {
		delete[] father;
	}
	// 查找索引为x的节点的父亲节点的索引
	int find(int x) {
		assert(x >= 0 && x < count);
		int a = x;
		while (x != father[x]) x = father[x];
		while (a != father[a]) {
			int z = a;
			a = father[a];
			father[z] = x;
		}
		return x;
	}
	
	void Union(int x, int y) {	
		int fx = find(x);
		int fy = find(y);
		if (fx != fy) father[fx] = fy;
	}
	
	bool isConnected(int x, int y) {
		return find(x) == find(y);
	}
};

c++ 压缩

0 人点赞