在本问题中, 树指的是一个连通且无环的无向图。
输入一个图，该图由一个有着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;
}
};
