题目描述
在本问题中，有根树指满足以下条件的有向图。该树只有一个根节点，所有其他节点都是该根节点的后继。每一个节点只有一个父节点，除了根节点没有父节点。
示例1
输入： [[1,2], [1,3], [2,3]] 输出： [2,3] 解释： 1 / \v v2-->3
示例2
输入： [[1,2], [2,3], [3,4], [4,1], [1,5]] 输出： [4,1] 解释： 5 <- 1 -> 2 ^ | | v 4 <- 3
提示
- 输入的二维数组大小在 到 。
- 二维数组中的整数在 到 之间，其中 是输入数组的大小。
题解
这题是上一道题 每日算法系列【LeetCode 684】冗余连接 的进阶版，区别就是无向图变成了有向图。
代码
c++
classSolution { public: staticconstintN=1010; intf[N], degree[N]; intn; vector<int>findRedundantDirectedConnection(vector<vector<int>>&edges) { n=edges.size(); memset(degree, 0, sizeofdegree); for (autoe : edges) ++degree[e[1]]; for (inti=n-1; i>=0; --i) { if (degree[edges[i][1]] ==2&&!wrongEdge(edges, i).size()) { returnedges[i]; } } returnwrongEdge(edges, n); } vector<int>wrongEdge(vector<vector<int>>&edges, intexcept) { init(); for (inti=0; i<n; ++i) { if (i==except) continue; intu=edges[i][0], v=edges[i][1]; if (same(u, v)) returnedges[i]; join(u, v); } return {}; } voidinit() { for (inti=1; i<=n; ++i) { f[i] =i; } } intfind(intu) { returnu==f[u] ?u : f[u]=find(f[u]); } voidjoin(intu, intv) { u=find(u); v=find(v); if (u==v) return; f[v] =u; } boolsame(intu, intv) { u=find(u); v=find(v); returnu==v; } };
python
classSolution: deffindRedundantDirectedConnection(self, edges: List[List[int]]) ->List[int]: self.n=len(edges) degree= [0] * (self.n+1) foru, vinedges: degree[v] +=1foru, vinedges[::-1]: ifdegree[v] ==2andlen(self.wrongEdge(edges, [u, v])) ==0: return [u, v] returnself.wrongEdge(edges, []) defwrongEdge(self, edges, ex): self.f= [iforiinrange(self.n+1)] foru, vinedges: if [u, v] ==ex: continueifself.same(u, v): return [u, v] self.join(u, v) return [] 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: returnself.f[v] =udefsame(self, u, v): u, v=self.find(u), self.find(v) returnu==v
作者简介：godweiyang，知乎同名，华东师范大学计算机系硕士在读，方向自然语言处理与深度学习。喜欢与人分享技术与知识，期待与你的进一步交流~
