Redundant Connection - II

In this approach, we have two cases to handle. The first one is that if a node has two parents then there are two answers and then we have to remove one edge from these two selected answers such that there is no cycle. The other case is that each node has one parent but the graph contains a cycle. So simply remove the edge that causes the cycle to form. Only ‘ANS1’ or ‘ANS2’ can be part of the cycle(if there is a cycle). So, if ‘ANS1’ is empty and cycle found (no 2 parent case, each node has 1 parent), return that edge since it's the last edge found which is part of the cycle. If ‘ANS1’ makes a cycle, return that. Otherwise, return ‘ANS2’ if it makes a cycle. If no cycle is found, then we can simply return ‘ANS2’ as we need to return the last edge in the edges list.

Refer to this doc for disjoint set union https://cp-algorithms.com/data_structures/disjoint_set_union.html

The steps are as follows:

• First, create a struct ‘DSU’ to perform disjoint-set union operations. In the struct define the find operation and union operation.
• We have to traverse over the edges twice. First to check for the nodes that have two parents and next traversal is for cycle detection.
• Create a map ‘PARENT’ to store the parent of a given node in order to identify if a node has two parents.
• Also, create two arrays ‘ANS1’ and ‘ANS2’ to store the edges when a node has two parents.
• Traverse over the given array of edges ‘ARR’ and for every edge do the following:
  • Find the source and the target from each edge.
  • Check that a node has already a parent or not. This is done as follows:
    • if('PARENT'[TARGEt] > 0) then there two edges at that node i.e 'ANS1' = {'PARENT'[TARGET] , ‘TARGET’} and ‘ANS2’ = {'SOURCE', ‘TARGET’}.
  • If not then simply do PARENT'[‘TARGET’] = 'SOURCE'.
• In the second traversal, we check which edge out of those two causes cycle.
  • If 'ANS2' = current Edge ‘ARR[i]’ then simply continue to the next edge in iteration because we have to return the last edge if there are multiple answers.
  • If not find 'SOURCE' and target and call union operation of structure ‘DSU’ and if it returns false that means there is a cycle then:
    • If ‘ANS1’ is empty then return the current edge ‘ARR[i]’.
    • Otherwise, return ‘ANS1’.
• If the second traversal does not return an edge then return ‘ANS2’ as the answer.

O(N), Where ‘N’ is the number of nodes in the graph.

Since traversing over all the N edges to find which node has two parents will take O(N) time and traversing over all the N edges again will take O(N) time and for every edge, and for each query through disjoint-set union we will reach nearly constant time. It turns out, that the final amortized time complexity is O(α(N)), where α(N) is the inverse Ackermann function, which grows very slowly which will give a total of O(N*α(N)) time. Thus total time complexity will be O(N + N*α(N)) = O(N) time.

O(N), Where ‘N’ is the number of nodes in the graph.

Since the current construction of the graph (embedded in our DSU structure) has at most ‘N’ nodes. Also, the map is used to store the parent of each node which will take O(N) space. Thus total space complexity will be O(N + N) = O(N) space.