在本问题中, 树指的是一个连通且无环的无向图。
输入一个图，该图由一个有着N个节点 (节点值不重复1, 2, …, N) 的树及一条附加的边构成。附加的边的两个顶点包含在1到N中间，这条附加的边不属于树中已存在的边。
结果图是一个以边组成的二维数组。每一个边的元素是一对[u, v] ，满足 u < v，表示连接顶点u 和v的无向图的边。
返回一条可以删去的边，使得结果图是一个有着N个节点的树。如果有多个答案，则返回二维数组中最后出现的边。答案边 [u, v] 应满足相同的格式 u < v。
输入: [[1,2], [1,3], [2,3]] 输出: [2,3]
思路： 就是找父节点以及合并两个节点的过程 优化 借助一个rank，这个rangk代表节点的高度（可以这么理解），将小的高度节点嫁接到高的节点上面。
代码
class Solution { private: vector<int> parent; vector<int> rank; int find_parent(int x) { int x_root=x; while(parent[x_root]!=-1) { x_root=parent[x_root]; } return x_root; } bool Union(int x,int y) { int x_root=find_parent(x); int y_root=find_parent(y); if(x_root==y_root) { return false; } //优化，防止形成的链太长 if(rank[x_root]>rank[y_root]) { parent[y_root]=x_root; } else if(rank[x_root]<rank[y_root]) { parent[x_root]=y_root; } else if(rank[x_root]==rank[y_root]) { parent[x_root]=y_root; rank[y_root]++; } return true; } public: vector<int> findRedundantConnection(vector<vector<int>>& edges) { vector<int> ret_v; int mi; int mj; int N=edges.size(); parent=vector<int> (N+1,-1);//刚开始父节点都是-1 rank=vector<int>(N+1,1);//刚开始每个节点的高度默认为1 for(int i=0;i<edges.size();i++) { if(Union(edges[i][0],edges[i][1])==false) { mi=edges[i][0]; mj=edges[i][1]; } } return ret_v=vector<int>{mi,mj}; } };