Union-Find is a data structure to check a cycle in the graph.

Every node in the graph has its own parent. So we need a parent array to should each node’s parent. Set the initial parent of each node to itself. And we need a rank array to show the height of the tree of each node as the root. Set the initial rank of each node to 1. And a variable count is needed to show the number of connected sections now. Set the initial count to the size fo the graph.

In the Find function, we need a implement path compression. That means when searching the parent recursively, modify all the node’s parent in the path to the final root.

In the Union function, we should find the two nodes’ roots. Then compare the rank of each root and set the root with a lower rank as the child. If the ranks are same, set one as the root and the other as the child. And let the new root’s rank plus one.

class UnionFind{

	private int[] parent;
	private int[] rank;
	private int count;

	public UnionFind(int n)
	{
		parent = new int[n];
		rank = new int[n];
		for(int i = 0; i < n; i++)
		{
			parent[i] = i;
			rank[i] = 1;
		}
		count = n;
	}

	public int find(int p)
	{
		return p != parent[p] ? parent[p] = find(parent[p]) : p;
	}

	public void union(int p, int q)
	{
		int pRoot = find(p);
		int qRoot = find(q);
		if(pRoot == qRoot)
		{
			return;
		}
		if(rank[pRoot] < rank[qRoot])
		{
			parent[pRoot] = qRoot;
		}
		else if(rank[pRoot] > rank[qRoot])
		{
			parent[qRoot] = pRoot;
		}
		else
		{
			parent[pRoot] = qRoot;
			rank[qRoot]++;
		}
	}

	public void show()
	{
		System.out.println("UnionFind:");
		for(int i = 0; i < count; i++)
		{
			System.out.println(i + " parent: " + parent[i] + " rank: " + rank[i]);
		}
	}

	public static void main(String[] Args)
	{
		UnionFind uf = new UnionFind(5);
		uf.show();
		uf.union(0, 1);
		uf.show();
		uf.union(1, 4);
		uf.show();
		uf.union(2, 3);
		uf.show();
		uf.union(0, 2);
		uf.show();
		uf.union(1, 3);
		uf.show();
		uf.union(0, 3);
		uf.show();
	}
}

Based on amortized analysis, the time of constructor is \(O(n)\). The time of Find and Union are approximately \(O(1)\).

Leave a Reply

Your email address will not be published. Required fields are marked *