Leetcode : Redundant Connections 2

Problem Statement

Solution:

The brute force approach for this problem would be to do a DFS or BFS starting from each node after removing edge Ei in the input 'edges' array. At each position i from right to left, after removing Ei, do BFS from each node in the graph. If for BFS from any node, we cover all the nodes from 1 to N without any cycle, then return edge Ei, because it implies that edge Ei is the last edge that creates a cycle.

For a directed graph with N nodes, BFS from all nodes is O(N2) time complexity and since we do BFS from all nodes at each edge Ei where the number of edges is N, the total time complexity of this approach is O(N3). But we can solve this problem in O(N2) overall time complexity.

Observe that if there is a cycle at any node 'n' of a directed graph, then there are two possible ways the cycle can be formed: Cycle formation at node n in directed graph

If there is a scenario like the one on the left, then the node 'n' must have two parent nodes in the graph. In such a case consider one of the parent and remove the other edge from the graph, if now the BFS from any node covers all the nodes from 1 to N without any cycle, then we have removed the correct edge else we have removed the incorrect edge and return the edge that we have not removed. This approach is O(N2) because to identify the such a node with two parents, we just have to scan O(N) number of edges.

If the scenario on the left does not occur, then the scenario on the right will definitely occur. In such scenario, since any node does not have two parents, remove each edge Ei from the back and instead of doing BFS from all nodes, we can do BFS from any node that has at-least one child node. Similar as earlier, if after removing edge Ei, we cover all the nodes from 1 to N without any cycle, then return edge Ei. This approach is also O(N2) because now we are not doing BFS from all nodes for each edge.

Below is the python code that solves this problem. Instead of doing BFS separately for the above two cases, we merge them into a single approach using a parent node pointer.

```class Solution(object):
def findRedundantDirectedConnection(self, edges):
parents = dict()
a, b, c, flag = -1, -1, float("Inf"), False

for i in range(len(edges)):
x, y = edges[i]
if y not in parents or parents[y] == x:
parents[y] = (x, i)

w = x
while w in parents:
w = parents[w]
if w == x or w == y:
if a != -1:
return edges[a]
else:
flag = True
c = min(c, i)
break

else:
a, b = parents[y], i

if a != -1:
return edges[a] if flag else edges[b]
else:
return edges[c]```

Categories: PROBLEM SOLVING