Problem statement

https://leetcode.com/problems/redundant-connection-ii/

Solution

As the problem states, there is one and only one edge that violates the definition of tree. Therefore, there are three possible cases:

  1. There is no cycle in the graph, but there exist two edges pointing to the same node
  2. There is a cycle, but there do not exist two edges pointing to the same node
  3. There is a cycle, and there exist two edges pointing to the same node.

First, go through the edges and detect if any node has two parents, i.e., if there exist two edges pointing to the same node. If there exists such two edges, record them as cand1 and cand2, because we know one of them must be the answer. If there do not exist such two edges, then cand1, cand2 will be None and there must be a cycle in the graph.

Just pretend the edges are undirected. Then go through the edges and do a regular union find, which can detect the existence of a cycle in an undirected graph. (Ignore the existence of cand2 when going through the edges, i.e., if [node1, node2] == cand2: continue}

  1. If there is no cycle, then we know cand2 must exist and it is the bad edge we are looking for.
  2. If there is a cycle and cand1, cand2 are not found, then the edge that incurs the cycle (the current edge when we go through the edges) is the bad edge.
  3. If there is a cycle and cand1, cand2 are found, then cand1 must be already in the cycle and it is the bad edge.

Here is the reason why cand2 is ignored in the union find process. When it is ignored, if a cycle is detected in the union find process, we know the cycle has nothing to do with cand2. Therefore, the answer must be cand1 if cand1 exists, or the edge incuring the cycle if cand1 does not exist. If no cycle is detected, then either cand1 or cand2 is the bad edge. But since cand2 appears later than cand1 in the list, we should return cand2.

Basically, we need to check all three possible cases above and make sure the code is working.

Complexity

Time and space complexity is O(n).

Code

#### borrowed code
class DisjointSet: #(UnionFind)
    def __init__(self, n):
        self.parent = list(range(n))
    
    def find(self, x):
        if self.parent[x] == x:
            return x
        return self.find(self.parent[x])
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y: return False
        self.parent[x] = self.parent[y]
        return True
    
class Solution:
    def findRedundantDirectedConnection(self, edges:):
        cand1, cand2, point_to = None, None, {}
        for node1, node2 in edges:
            if node2 in point_to: 
                cand1, cand2 = point_to[node2], [node1, node2]
                break
            point_to[node2] = [node1, node2]
            
        ds = DisjointSet(len(edges))
        for node1, node2 in edges:
            if [node1, node2] == cand2: continue
            if not ds.union(node1 - 1, node2 - 1):
                if cand1: return cand1
                return [node1, node2]
        return cand2

there is visualization of these cases (cases 2 and 3 need to be swapped)

image.png