// file wtunion.h
// union/find using weighting and collapsing rules

#ifndef UnionFind_
#define UnionFind_


class UnionFind 
{
public:
	UnionFind(int Size = 10);
	~UnionFind() 
	{
		delete [] parent;
		delete [] root;
	}
	void Union(int, int);
	int Find(int);
private:
	int *parent;  // parent array
	bool *root;   // root[i] is true iff i is a root
};

UnionFind::UnionFind(int n)
{// One element per set/class/tree.
	root = new bool[n+1];
	parent = new int[n+1];
	
	for (int e = 1; e <= n; e++) 
	{
		parent[e] = 1;
		root[e] = true;
	}
}

int UnionFind::Find(int e)
{// Return root of tree containing e.
	// Compact path from e to root.
	int j = e;
	// find root
	while (!root[j])
		j = parent[j];
	
	// compact
	int f = e;  // start at e
	while (f != j) 
	{// f is not root
		int pf = parent[f];
		parent[f] = j;  // move f to level 2
		f = pf;
	}        // f moves to old parent 
	
	return j;
}

void UnionFind::Union(int i, int j)
{// Combine trees with roots i and j.
	if (parent[i] < parent[j]) 
	{
		// i becomes subtree of j
		parent[j] += parent[i];
		root[i] = false;
		parent[i] = j; 
	}
	else 
	{// j becomes subtree of i
		parent[i] += parent[j];
		root[j] = false;
		parent[j] = i;
	}
}

#endif;