Geeks Union-Find Algorithm Union By Rank and Path Compression 圖環算法

同樣是查找一個圖是否有環的算法，但是這個算法很牛逼，構造樹的時候可以達到O(lgn)時間效率。n代表頂點數

原因是根據需要縮減了樹的高度，也叫壓縮路徑（Path compression），名字很高深，不過其實不難了解，簡單來說就是每次查找一個節點的時候，都把這一路徑中的所有節點都賦予根節點作為路徑。

原文沒指出的地方：

也因為需要壓縮，是以初始化的時候注意，不能如前面簡單實用Union Find的算法那樣初始化所有頂點的父母節點為-1，應該是初始化所有節點的父母節點為本身（自己繁殖自己？），然後就友善遞歸的時候一律可以傳回這個跟節點了。 

當然其實初始化為-1也是可以的，不過需要額外代碼處理一下，也不難。

最後可以參考原文：http://www.geeksforgeeks.org/union-find-algorithm-set-2-union-by-rank/

#pragma once
#include <iostream>

class UnionFindUnionByRank
{
	struct Edge
	{
		int src, des;
	};

	struct Graph
	{
		int V, E;
		Edge *edges;
		Graph(int v, int e) : V(v), E(e)
		{
			edges = new Edge[e];
		}
		~Graph()
		{
			if (edges) delete [] edges;
		}
	};

	struct subSet
	{
		int parent, rank;
	};

	int find(subSet *subs, int i)
	{
		//因為要壓縮，是以不能使用-1作為根的标志了
		if (subs[i].parent != i)
		{
			//Union by rank: attach smaller rank tree to high rank tree. It is so simple, but very hard to create it totally by ourself, so it's good to stand on the shoulder of the giant.
			subs[i].parent = find(subs, subs[i].parent);
		}
		return subs[i].parent;//因為如果-1作為根标志，那麼這裡就要傳回i，就達不到壓縮的效果了，而是應該傳回parent，一層一層遞歸回上一層。
	}

	void unionTwo(subSet *subs, int x, int y)
	{
		int xroot = find(subs, x);
		int yroot = find(subs, y);

		if (subs[xroot].rank < subs[yroot].rank)
		{
			subs[xroot].parent = yroot;
		}
		else if (subs[xroot].rank > subs[yroot].rank)
		{
			subs[yroot].parent = xroot;
		}
		else
		{
			//only need to increment its rank when ther are equal rank
			subs[yroot].parent = xroot;
			subs[xroot].rank++;
		}
	}

	bool isCycle(Graph *gra)
	{
		subSet *subs = new subSet[gra->V];
		for (int i = 0; i < gra->V; i++)
		{
			subs[i].parent = i;//parent不能初始化為-1
			subs[i].rank = 0;
		}

		for (int e = 0; e < gra->E; e++)
		{
			int x = find(subs, gra->edges[e].src);
			int y = find(subs, gra->edges[e].des);

			if (x == y) return true;

			unionTwo(subs, x, y);
		}

		return false;
	}
public:
	UnionFindUnionByRank()
	{
		int V = 3, E = 3;
		struct Graph* graph = new Graph(V, E);

		// add edge 0-1
		graph->edges[0].src = 0;
		graph->edges[0].des = 1;

		// add edge 1-2
		graph->edges[1].src = 1;
		graph->edges[1].des = 2;

		// add edge 0-2
		graph->edges[2].src = 0;
		graph->edges[2].des = 2;

		if (isCycle(graph))
			printf( "Union By Rank found graph contains cycle \n" );
		else
			printf( "Union By Rank found graph doesn't contain cycle \n" );
	}
};