基本思想：

　　Union Find问题主要用于解决分块问题，对于Union Find问题一般也可以用DFS或BFS解决，但用Union Find更方便一些。该算法一般包含两个函数，Union和Find函数，Find函数就是依据图或树的拓扑关系找到其根节点，Union则是将两个子图或子树合并成一个树。

　　具体实现可看如下代码，parent数组存储了当前节点的父节点，如果当前节点为根节点，则其父节点为自己，所以递归调用Find函数直至其父节点等于自身即找到根节点。

　　Union函数略复杂，其多了一个rank数组，该数组的作用是决定将子图的合并方式，即rank值小的向rank值大的图合并，直观上来说，就是小图向大图合并。如果两图大小相等，则将第二张图向第一张图合并，并将第一张图的rank值加一。

1 class Solution { 2 public: 3     int Find(vector
     
       &parent,int target){ 4         if(parent[target] == target) 5             return target; 6         return Find(parent,parent[target]); 7     } 8     void Union(vector
      
        &parent,vector
       
         &rank,int v1,int v2){ 9         int p1 = Find(parent,v1);10         int p2 = Find(parent,v2);11         if(p1 == p2) return;12         if(rank[p1] > rank[p2]) parent[p2] = p1;13         else if(rank[p1] < rank[p2]) parent[p1] = p2;14         else{15             parent[p2] = p1;16             rank[p1]++;17         }18     }19 }