C++刷leetcode（684. 冗余连接）【并查集】

糖逗

题目描述：

1. 在本问题中, 树指的是一个连通且无环的无向图。
   
2. 
   
3. 输入一个图，该图由一个有着N个节点 (节点值不重复1, 2, ..., N) 的树及一条附加的边构成。附加的边的两个顶点包含在1到N中间，这条附加的边不属于树中已存在的边。
   
4. 
   
5. 结果图是一个以边组成的二维数组。每一个边的元素是一对[u, v]&#160;，满足&#160;u < v，表示连接顶点u&#160;和v的无向图的边。
   
6. 
   
7. 返回一条可以删去的边，使得结果图是一个有着N个节点的树。如果有多个答案，则返回二维数组中最后出现的边。答案边&#160;[u, v] 应满足相同的格式&#160;u < v。
   
8. 
   
9. 示例 1：
   
10. 
    
11. 输入: [[1,2], [1,3], [2,3]]
    
12. 输出: [2,3]
    
13. 解释: 给定的无向图为:
    
14.   1
    
15. / \
    
16. 2 - 3
    
17. 示例 2：
    
18. 
    
19. 输入: [[1,2], [2,3], [3,4], [1,4], [1,5]]
    
20. 输出: [1,4]
    
21. 解释: 给定的无向图为:
    
22. 5 - 1 - 2
    
23.     |   |
    
24.     4 - 3
    
25. 注意:
    
26. 
    
27. 输入的二维数组大小在 3 到 1000。
    
28. 二维数组中的整数在1到N之间，其中N是输入数组的大小。
    
29. 更新(2017-09-26):
    
30. 我们已经重新检查了问题描述及测试用例，明确图是无向&#160;图。对于有向图详见冗余连接II。对于造成任何不便，我们深感歉意。
    
31. 
    
32. 来源：力扣（LeetCode）
    
33. 链接：https://leetcode-cn.com/problems/redundant-connection
    
34. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. class Solution {
   
2. public:
   
3.     int find_root(int x, vector<int>&father){
   
4.         if(x != father[x]) return find_root(father[x], father);
   
5.         return x;
   
6.     }
   
7.     bool uniton(int x, int y, vector<int>&father){
   
8.         int temp1 = find_root(x, father);
   
9.         int temp2 = find_root(y, father);
   
10.         if(temp1 != temp2){
    
11.             father[temp1] = temp2;
    
12.             return false;
    
13.         }
    
14.         return true;
    
15.     }
    
16.     vector<int> findRedundantConnection(vector<vector<int>>& edges) {
    
17.         int len = edges.size();
    
18.         vector<int> father(len+1, 0);
    
19.         for(int i = 0; i <= len; i++){
    
20.             father[i] = i;
    
21.         }
    
22.         for(auto cha : edges){
    
23.             if(uniton(cha[0], cha[1], father)){
    
24.                 return cha;
    
25.             }
    
26.         }
    
27.         return {};
    
28.     }
    
29. };

复制代码

注意事项
1.返回的是使点成环的最后一条边