#include "disjoint_set.h"

DisjointSet::DisjointSet(int size)
{
	this->size_ = size;
	this->parents_ = new int[this->size_];

	for (int i = 0; i < this->size_; i++)
	{
		// 初始化每个结点都是根
		this->parents_[i] = -1;
	}
}

void DisjointSet::_union(int node1, int node2)
{
	// 获取根结点
	int root1 = this->findRecursive(node1);
	int root2 = this->findRecursive(node2);

	// 判断是否已经合并
	if (root1 == root2)
		return;

	// 合并
	// // parents_[root1]更新(root1作为合并后集合的根结点)
	this->parents_[root1] += this->parents_[root2];
	// // root1成为结点root2的父结点
	this->parents_[root2] = root1;
}

int DisjointSet::findRecursive(int index)
{
	if (this->parents_[index] < 0)
		return index;
	return this->findRecursive(parents_[index]);
}

void DisjointSet::weightedUnion(int node1, int node2)
{
	// 获取各自的根结点
	int root1 = this->findRecursive(node1);
	int root2 = this->findRecursive(node2);

	// 判断是否已经合并
	if (root1 = root2)
		return;

	// 合并
	int new_weight = this->parents_[root1] + this->parents_[root2];

	// 这里的if-else语句的作用是小树挂载到大树下面
	if (this->parents_[root1] > this->parents_[root2])
	{
		this->parents_[root1] = root2;
		this->parents_[root2] = new_weight;
	}
	else
	{
		this->parents_[root2] = root1;
		this->parents_[root1] = new_weight;
	}
}

int DisjointSet::find(int index)
{
	int root = index;
	while (this->parents_[root] >= 0)
	{
		root = this->parents_[root];
	}

	// 之后root就是当前并查集（多叉树）的根结点

	// 优化策略，目的是把index到root路径上的所有的元素都直接挂到根结点下面
	int parent_index;
	while (index != root)
	{
		parent_index = this->parents_[index];
		this->parents_[index] = root;
		index = parent_index;
	}

	return root;
}