#pragma once

class DisjointSet
{
private:
	int size_;		// 数组大小
	int* parents_;	// 父节点数组，下标代表结点，对应下标存储的值代表父节点。如，parents_[index] = parent_index;index代表当前结点，parent_index代表当前结点的父节点

public:
	explicit DisjointSet(int size);

	~DisjointSet() { delete[] this->parents_; }

	// 合并
	void _union(int node1, int node2);

	// 查找（递归）
	int findRecursive(int index);

	// 合并集合（Weighted）
	void weightedUnion(int node1,int node2);

	// 查找
	int find(int index);
};