Redundant Connection Ii - Leetcode Solution

Problem Statement:

In this problem we are given a directed graph represented as a list of edges. It is guaranteed that there are no self-loops or multiple edges between any two vertices.

We need to find and remove a redundant directed edge such that after removing the edge, the directed graph remains acyclic. If there are multiple answers, then return any of them.

If the graph is already acyclic, then return the original graph.

Solution:

This problem is a variation of the classic problem of detecting a cycle in a directed graph. The basic idea is to use DFS to traverse the graph and check if there exists a cycle.

We can split this problem into two cases.

1. There are no nodes with indegree 2: In this case, the graph can only have one cycle. We can use DFS to traverse the graph and mark visited nodes. If we reach a node that is already marked as visited, then we have detected a cycle. We can return the last edge that is part of the cycle.

2. There are nodes with indegree 2: In this case, the graph can have multiple cycles. We will need to remove one edge at a time and check if the graph becomes acyclic. We can do this by removing each edge and checking if the graph is still connected. If it is not connected, then the removed edge was part of a cycle and we can return it. If it is connected but still has a cycle, then it means that there is another edge in the graph that is part of the cycle. In this case, we will remove the other edge and check again until we find the edge that is part of the cycle.

We can use a few helper functions to implement this approach. To keep track of the indegree of each node, we can use a dictionary or a list. To check if the graph is connected after removing an edge, we can use either DFS or BFS.

Time Complexity:

The time complexity of this solution is O(N^2) in the worst case where N is the number of nodes in the graph. This is because we need to check each edge one by one to find the redundant edge.

Space Complexity:

The space complexity of this solution is O(N) because we need to store the indegree of each node in a dictionary or a list.

1