@1337c0d3r For [[2,1],[3,1],[4,2],[1,4]], shouldn't the answer be [1,4] instead of [2,1]? Which is edge that occurs last in the given 2D-array.
Well, this is answered in another thread.
This is because node 1 has two parents 2 and 3, so only removing [2,1] can eliminate both the cycle and the extra parent. @JadenPan IMHO [1,4] and [2,1] can be a better example to illustrate case 3.
def findRedundantDirectedConnection(self, edges):
first, second, n = None, None, len(edges)
ds = ''.join(map(chr, range(n+1)))
ind = [0 for _ in range(n+1)]
for p, q in edges: ind[q] += 1
for p, q in edges:
if ind[q] > 1:
second = [p, q]
first = [p, q]
if ds[p] == ds[q]:
return first if first else [p, q]
ds = ds.replace(ds[p], ds[q])
[4,2] is the right answer. If you delete 2,4 then the graph looks like:
2 < - 5 - > 3
which is not a rooted tree. Recall the definition for rooted tree, in the problem statement:
A rooted tree is a directed graph such that, there is exactly one node (the root) for which all other nodes are descendants of this node, plus every node has exactly one parent, except for the root node which has no parents.
Here, 1 or 4 are the only nodes with no parents; furthermore, 4 is not a descendant of 1 and vice versa.