Redundant Connection

Problem Statement

You are given a connected undirected graph with n nodes labeled from 1 to n. Initially, it contained no cycles and consisted of n-1 edges.

We have now added one additional edge to the graph. The edge has two different vertices chosen from 1 to n, and was not an edge that previously existed in the graph.

The graph is represented as an array edges of length n where edges[i] = [ai, bi] represents an edge between nodes ai and bi in the graph.

Return an edge that can be removed so that the graph is still a connected non-cyclical graph. If there are multiple answers, return the edge that appears last in the input edges.

Example 1:

Input: edges = [[1,2],[1,3],[3,4],[2,4]]

Output: [2,4]

Example 2:

Input: edges = [[1,2],[1,3],[1,4],[3,4],[4,5]]

Output: [3,4]

Constraints:

• n == edges.length
• 3 <= n <= 100
• 1 <= edges[i][0] < edges[i][1] <= edges.length
• There are no repeated edges and no self-loops in the input.

You should aim for a solution as good or better than O(V + E) time and O(V) space, where V is the number vertices and E is the number of edges in the graph.

Recommended Time and Space Complexity

You should aim for a solution as good or better than O(V + E) time and O(V) space, where V is the number vertices and E is the number of edges in the graph.

Hint 1

There will be only one edge that creates the cycle in the given problem. Why? Because the graph is initially acyclic, and a cycle is formed only after adding one extra edge that was not present in the graph initially. Can you think of an algorithm that helps determine whether the current connecting edge forms a cycle? Perhaps a component-oriented algorithm?

Hint 2

We can use the Union-Find (DSU) algorithm to create the graph from the given edges. While connecting the edges, if we fail to connect any edge, it means this is the redundant edge, and we return it. How would you implement this?

Hint 3

Create a DSU (Disjoint Set Union) class and traverse through the given edges. For each edge, attempt to connect the nodes using the union function. If the union function returns false, indicating that the current edge forms a cycle, we immediately return that edge.

Solution

Disjoint Set Union

def find_redundant_connection(edges: list[list[int]]) -> list[int]:
    parent = [i for i in range(len(edges) + 1)]
    rank = [1] * (len(edges) + 1)

    def find(n: int) -> int:
        p = parent[n]
        while p != parent[p]:
            parent[p] = parent[parent[p]]
            p = parent[p]
        return p

    def union(n1: int, n2: int) -> bool:
        p1, p2 = find(n1), find(n2)

        if p1 == p2:
            return False
        if rank[p1] > rank[p2]:
            parent[p2] = p1
            rank[p1] += rank[p2]
        else:
            parent[p1] = p2
            rank[p2] += rank[p1]
        return True

    for n1, n2 in edges:
        if not union(n1, n2):
            return [n1, n2]
    return []

Time complexity: O(V + (E * A(V))) Space complexity: O(V)