Solution:

The brute force approach for this problem would be to do a DFS or BFS starting from each node after removing edge E_{i} in the input 'edges' array. At each position i from right to left, after removing E_{i}, 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 E_{i}, because it implies that edge E_{i} is the last edge that creates a cycle.

For a directed graph with N nodes, BFS from all nodes is O(N^{2}) time complexity and since we do BFS from all nodes at each edge E_{i} where the number of edges is N, the total time complexity of this approach is O(N^{3}). But we can solve this problem in O(N^{2}) 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:

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(N^{2}) 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 E_{i} 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 E_{i}, we cover all the nodes from 1 to N without any cycle, then return edge E_{i}. This approach is also O(N^{2}) 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][0] == x: parents[y] = (x, i) w = x while w in parents: w = parents[w][0] 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][1], i if a != -1: return edges[a] if flag else edges[b] else: return edges[c]

Categories: PROBLEM SOLVING

Tags: BFS, Cycle Graph, DFS, Directed Graph, Leetcode, Redundant Connection

### Leave a Reply

You must be logged in to post a comment.