并查集(1)-判斷無向圖是否存在環

并查集是一種樹型的資料結構，用于處理一些不相交集合（Disjoint Sets）的合并及查詢問題。常常在使用中以森林來表示。集就是讓每個元素構成一個單元素的集合，也就是按一定順序将屬于同一組的元素所在的集合合并。

Find：确定元素屬于哪一個子集。它可以被用來确定兩個元素是否屬于同一子集合。

Union：将兩個子集合并成同一個集合。

其實判斷一個圖是否存在環已經有相應的算法，此文用并查集來判斷一個圖是否有環。

我們可以用一個一維數組parent[] 來記錄子集合。

看下面這個圖：

對每一條邊的兩個頂點加入集合，發現兩個相同的頂點在一個子集合中，就說明存在環。

初始化：parent[n] 的每個元素都為-1，共有n個子集合，表示集合隻有目前頂點一個元素。

然後逐個處理每條邊。

邊0-1：我們找到兩個子集合 0 和1，因為他們在不同的子集合，現在需要合并他們(Union). 把其中一個子集合作為對方的父集合.

邊0-2:1屬于屬于子集合1,2屬于子集合2，是以合并他們。

 邊0-2: 0是在子集和2和2也是在子集合2， 因為 0->1->2 // 1 是0 父集合 并且  2 是1的父集合 。是以，找到了環。

代碼：