Template class disjoint-set data structure usefull for Kruskal's algorithm. A Disjoint-set data structure is a data structure that keeps track of a set of elements partitioned into a number of disjoint (nonoverlapping) subsets. A union-find algorithm is an algorithm that performs two useful operations on such a data structure: Find: Determine wh…

UnionFind.hpp

#pragma once

// @author Nicolas Roy @niroyb
// @date 2013-04-22
// Disjoint set data structure aka unionfind
// Time complexity of log(n) for all operations because of map.find()

#include <map>

template<class verticeType>
class UnionFind
{
public:
	//Tries to to merge the groups of two vertices
	//Returns true on success (vertices were in different groups)
	//Returns false on failure (vertices were in the same group)
	bool unite(verticeType x, verticeType y);

	//Returns the parent vertice of the group of x
	verticeType find(verticeType x);

private:
	map<verticeType, verticeType> parent;
	map<verticeType, unsigned int> rank;
};

template<class verticeType>
bool UnionFind<verticeType>::unite( verticeType x, verticeType y)
{
	verticeType xRoot = find(x);
	verticeType yRoot = find(y);
	//x and y are in the same set
	if (xRoot == yRoot)
		return false;

	// Merge the sets of x and y
	// Attach the smaller tree to the root of the larger tree
	if (rank[xRoot] < rank[yRoot])
		parent[xRoot] = yRoot;
	else if (rank[xRoot] > rank[yRoot])
		parent[yRoot] = xRoot;
	else
	{
		parent[yRoot] = xRoot;
		rank[xRoot] += 1;
	}
	return true;
}

template<class verticeType>
verticeType UnionFind<verticeType>::find( verticeType x )
{
	//Make node if nonexistent
	if (parent.find(x) == parent.end())
	{
		parent[x] = x;
		rank[x] = 0;
	}

	//Find parent and do path compression
	if (parent[x] != x)
		parent[x] = find(parent[x]);
	return parent[x];
}