# Short solutions, finding nodes' parent

• Inputs guarantee only one edge needs to be removed to make the directed graph a tree, so there are only two cases where an edge needs to be deleted:

1. An edge that makes a node having more than one parents;
2. An edge that cause a loop.

For each edge (u -> v), we firstly check whether the child (v) has already had a parent. If not, only an edge that connect the root and its descendent can make a loop. So we only need to check whether v is u's root.

C++:

``````vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {
unordered_map<int, int> parents;   // record tree nodes and its parents
for (int i = 0; i < edges.size(); i++) {
if (parents.find(edges[i][1]) != parents.end()) return edges[i]; //more than one parents
int p = edges[i][0];   // finding u's root
while (parents.find(p) != parents.end()) p = parents[p];
if (p == edges[i][1]) return edges[i];
parents[edges[i][1]] = edges[i][0];
}
return {};
}
``````

Python:

``````def findRedundantDirectedConnection(self, edges):
parents = {}
for e in edges:
if e[1] in parents: return e
p = e[0]
while p in parents: p = parents[p]
if p == e[1]: return e
parents[e[1]] = e[0]
return []

``````

• This code fails at:
Input:
[[2,1],[3,1],[4,2],[1,4]]
Output:
[3,1]
Expected:
[2,1]

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.