题目描述
在本问题中, 树指的是一个连通且无环的无向图。
输入一个图，该图由一个有着 个节点（节点值不重复 ）的树及一条附加的边构成。附加的边的两个顶点包含在 到 中间，这条附加的边不属于树中已存在的边。
结果图是一个以边组成的二维数组。每一个边的元素是一对 ，满足 ，表示连接顶点 和 的无向图的边。
返回一条可以删去的边，使得结果图是一个有着 个节点的树。如果有多个答案，则返回二维数组中最后出现的边。答案边 应满足相同的格式 。
示例1
输入： [[1,2], [1,3], [2,3]] 输出： [2,3] 解释： 1 / \2 - 3
示例2
输入： [[1,2], [2,3], [3,4], [1,4], [1,5]] 输出： [1,4] 解释： 5 - 1 - 2 | | 4 - 3
提示
下面讲两个常用的并查集优化。
代码
c++
classSolution { public: staticconstintN=1010; intf[N], rank[N]; vector<int>findRedundantConnection(vector<vector<int>>&edges) { init(); for (autoe : edges) { intu=e[0], v=e[1]; if (same(u, v)) return {u, v}; elsejoin(u, v); } return {-1, -1}; } voidinit() { for (inti=0; i<N; ++i) { f[i] =i; rank[i] =1; } } intfind(intu) { returnu==f[u] ?u : f[u]=find(f[u]); } voidjoin(intu, intv) { u=find(u); v=find(v); if (u==v) return; if (rank[u] <rank[v]) { f[u] =v; } else { f[v] =u; if (rank[u] ==rank[v]) { rank[u]++; } } } boolsame(intu, intv) { u=find(u); v=find(v); returnu==v; } };
python
classSolution: deffindRedundantConnection(self, edges: List[List[int]]) ->List[int]: n=len(edges) self.f= [iforiinrange(n+1)] self.rank= [1] * (n+1) for [u, v] inedges: ifself.same(u, v): return [u, v] else: self.join(u, v) deffind(self, u): ifu==self.f[u]: returnuself.f[u] =self.find(self.f[u]) returnself.f[u] defjoin(self, u, v): u, v=self.find(u), self.find(v) ifu==v: returnifself.rank[u] <self.rank[v]: self.f[u] =velse: self.f[v] =uifself.rank[u] ==self.rank[v]: self.rank[u] +=1defsame(self, u, v): u, v=self.find(u), self.find(v) returnu==v
作者简介：godweiyang，知乎同名，华东师范大学计算机系硕士在读，方向自然语言处理与深度学习。喜欢与人分享技术与知识，期待与你的进一步交流~
