684. 冗余连接

在本问题中, 树指的是一个连通且无环的无向图。
输入一个图，该图由一个有着N个节点 (节点值不重复1, 2, ..., N) 的树及一条附加的边构成。附加的边的两个顶点包含在1到N中间，这条附加的边不属于树中已存在的边。

结果图是一个以边组成的二维数组。每一个边的元素是一对[u, v] ，满足 u < v，表示连接顶点u 和v的无向图的边。

返回一条可以删去的边，使得结果图是一个有着N个节点的树。如果有多个答案，则返回二维数组中最后出现的边。答案边 [u, v] 应满足相同的格式 u < v。

解决方案

并查集：
并查集（Union-find Sets）是一种非常精巧而实用的数据结构，它主要用于处理一些不相交集合的合并问题。一些常见的用途有求连通子图、求最小生成树的 Kruskal 算法和求最近公共祖先（Least Common Ancestors, LCA）等。
开始时，每个元素各自属于一个集合，之后根据条件，将属于同一个组的集合进行合并。

并查集的基本操作有三个：

makeSet(s)：建立一个新的并查集，其中包含 s 个单元素集合。
unionSet(x, y)：把元素 x 和元素 y 所在的集合合并，要求 x 和 y 所在的集合不相交，如果相交则不合并。
find(x)：找到元素 x 所在的集合的代表，该操作也可以用于判断两个元素是否位于同一个集合，只要将它们各自的代表比较一下就可以了。
对于本题而言，可以将具有相同根节点的集合合并为同一个集合。对于一棵树而言，每条边都会把一个新的节点加入到集合中。如果一条边的两个节点已经在同一个节点中，则该边是冗余边。
具体实现如下：

class Solution {
public:
    int find(int x, vector<int>& parent)
    {
        while(x != parent[x])
        {
            x = parent[x];
        }
        return x;
    }
    bool union_node(int x, int y, vector<int>& parent)
    {
        int px = find(x, parent);
        int py = find(y, parent);
        if(px != py)
        {
            parent[py] = px;
            return true; 
        }
        return false;
    }
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        int n = edges.size();
        vector<int> parent(n + 1);
        for(int i=1;i<=n;i++)
        {
            parent[i] = i;
        }
        for(int i=0;i<n;i++)
        {
            if(!union_node(edges[i][0], edges[i][1], parent))
            {
                return edges[i];
            }
        }
        vector<int> res;
        return res;
    }
};