#include "UnionFind.h"
#include<iostream>
using namespace std;

int UnionFind::getunioncount()
{
	return unionsize.size();
}

UnionFind::UnionFind(vector<int> myList)//캯
{
	for (int val : myList) {
		element* ele = new element(val);
		elements[val] = ele;
		fathers[ele] = ele;
		unionsize[ele] = 1;
	}
}

element* UnionFind::findroot(element* c_element)
{
	stack<element *> stk;
	element* ele = c_element;
	element* father = fathers[ele];
	while (ele != father) {
		stk.push(ele);
		ele = father;
		father = fathers[ele] ;
	}
	while (!stk.empty()) {
		fathers[stk.top()] = father;
		stk.pop();
	}
	return father;
}

bool UnionFind::issameset(int a, int b)
{
	if (elements.find(a) != elements.end() && elements.find(b) != elements.end()) {
		if (findroot(elements[a]) == findroot(elements[b])) {
			return true;
		}
	}
	return false;
}

void UnionFind::Union(int a, int b)
{
	if (elements.find(a) != elements.end() && elements.find(b) != elements.end()) {
		if (!issameset(a,b)) {
			element* atopleader = findroot(elements[a]);
			element* btopleader = findroot(elements[b]);
			int arootsize = unionsize[elements[a]];
			int brootsize = unionsize[elements[b]];
			element* big = arootsize >= brootsize ? atopleader : btopleader;
			element* small = big == atopleader ? btopleader : atopleader;
			fathers[small] = big;
			unionsize[big] = arootsize + brootsize;
			unionsize.erase(small);

		}
	}
}

void UnionFind::print()
{
	for (auto p : unionsize) {
		cout << p.first->value << "ԱΪ" << p.second << endl;
	}
}