Solution Explanation for Redundant Connection II

This problem asks to find an edge to remove from a graph to make it a valid rooted tree. The input is a directed graph represented as a list of edges, where an extra edge has been added to a rooted tree. This extra edge can create either a node with in-degree 2 or a cycle.

The solutions use Union-Find to efficiently detect cycles. Union-Find is a data structure that keeps track of connected components in a graph. The core idea is to assign each node a representative (parent). If two nodes have the same representative, they are connected. We can union two nodes by setting the representative of one to the representative of the other. We can find the representative of a node using path compression for optimization.

Approach:

1. Detect Duplicate Edges: First, we scan the edges and identify the node with an in-degree of 2 (meaning it has two incoming edges). This is an indicator of the added edge that needs to be dealt with. There can be two candidate edges. We store their indices in the dup list.

2. Handle Duplicate Edges: If dup is not empty, it means we have a node with two incoming edges. This can cause two scenarios: either a cycle is present or not. The approach involves a Union-Find to check connectivity. We temporarily ignore one of the duplicate edges, and perform Union-Find operations on other edges. If we encounter a cycle, that means the ignored edge was the correct one to remove. If no cycle is found, we return the other candidate edge.

3. Detect Cycles Without Duplicate Edges: If dup is empty, it means there's no node with in-degree 2 and only a cycle is present. In this case, we proceed with Union-Find, and the edge that creates a cycle is the edge that needs to be removed.

Time Complexity Analysis:

• Union-Find Operations: The find and union operations in Union-Find with path compression and union by rank have an amortized time complexity of almost O(1) per operation, approaching O(α(n)), where α(n) is the inverse Ackermann function, which is practically a constant. Since there are n operations, the overall complexity for this part is O(n).
• Edge Traversal: The initial scans of edges to compute in-degrees and check for duplicate edges take O(n) time.

Therefore, the overall time complexity is dominated by the Union-Find operations and edge traversal, resulting in O(n).

Space Complexity Analysis:

The space complexity is determined by:

• ind array: O(n)
• dup list: O(1) (at most two entries).
• p array in Union-Find: O(n)

Therefore, the space complexity is O(n).

Code Example (Python):

class UnionFind:
    def __init__(self, n):
        self.p = list(range(n))
        self.size = [1] * n
 
    def find(self, x):
        if self.p[x] != x:
            self.p[x] = self.find(self.p[x])
        return self.p[x]
 
    def union(self, a, b):
        pa, pb = self.find(a), self.find(b)
        if pa == pb:
            return False
        if self.size[pa] > self.size[pb]:
            self.p[pb] = pa
            self.size[pa] += self.size[pb]
        else:
            self.p[pa] = pb
            self.size[pb] += self.size[pa]
        return True
 
class Solution:
    def findRedundantDirectedConnection(self, edges):
        n = len(edges)
        ind = [0] * (n + 1)
        for u, v in edges:
            ind[v] += 1
        dup = []
        for i, (u, v) in enumerate(edges):
            if ind[v] == 2:
                dup.append(i)
        uf = UnionFind(n + 1)
        if dup:
            for i, (u, v) in enumerate(edges):
                if i == dup[1]:
                    continue
                if not uf.union(u, v):
                    return edges[dup[0]]
            return edges[dup[1]]
        for u, v in edges:
            if not uf.union(u, v):
                return [u, v]
 

The code in other languages (Java, C++, Go, TypeScript, JavaScript) follows a very similar structure, implementing the Union-Find data structure and the main logic as described above. The only difference is syntax.