Redundant Connection

In this problem, a tree is an undirected graph that is connected and has no cycles.

You are given a graph that started as a tree with n nodes labeled from 1 to n, with one additional edge added. The added edge has two different vertices chosen from 1 to n, and was not an edge that already existed. The graph is represented as an array edges of length n where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi in the graph.

Return an edge that can be removed so that the resulting graph is a tree of n nodes. If there are multiple answers, return the answer that occurs last in the input.

Example 1:

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

Example 2:

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

Constraints:

• n == edges.length
• 3 <= n <= 1000
• edges[i].length == 2
• 1 <= ai < bi <= edges.length
• ai != bi
• There are no repeated edges.
• The given graph is connected.

Approach: Union-Find Detecting the Cycle Edge

Algorithm

1. Union the endpoints of each edge in order
2. If both endpoints already belong to the same set, adding this edge creates a cycle
3. The first such edge encountered is the redundant one; because we scan in order, it is also the one occurring last in the input

Time & Space Complexity

• Time Complexity: O(n * α(n)) - α is the inverse Ackermann function (nearly constant with path compression)
• Space Complexity: O(n) - the parent and rank arrays

Java Implementation

import java.util.Arrays;

public class RedundantConnection {

    private int[] parent;
    private int[] rank;

    /**
     * Return an edge that can be removed to make the graph a tree.
     * @param edges Edges of the graph
     * @return The redundant edge occurring last in the input
     */
    public int[] findRedundantConnection(int[][] edges) {
        int n = edges.length;
        parent = new int[n + 1];
        rank = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            parent[i] = i;
        }

        for (int[] edge : edges) {
            int a = edge[0];
            int b = edge[1];
            if (find(a) == find(b)) {
                return edge;
            }
            union(a, b);
        }
        return new int[0];
    }

    private int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    private void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX == rootY) {
            return;
        }
        if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
        } else {
            parent[rootY] = rootX;
            rank[rootX]++;
        }
    }

    // Test method
    public static void main(String[] args) {
        RedundantConnection rc = new RedundantConnection();
        int[][] edges1 = {{1, 2}, {1, 3}, {2, 3}};
        System.out.println("Input: edges = [[1,2],[1,3],[2,3]]");
        System.out.println("Output: " + Arrays.toString(rc.findRedundantConnection(edges1))); // Expected: [2,3]

        int[][] edges2 = {{1, 2}, {2, 3}, {3, 4}, {1, 4}, {1, 5}};
        System.out.println("Input: edges = [[1,2],[2,3],[3,4],[1,4],[1,5]]");
        System.out.println("Output: " + Arrays.toString(rc.findRedundantConnection(edges2))); // Expected: [1,4]
    }
}

Example Walkthrough

For edges = [[1,2],[1,3],[2,3]]:

1. Union(1,2): sets {1,2}
2. Union(1,3): sets {1,2,3}
3. Edge [2,3]: both endpoints already share a root -> this is the redundant edge

Answer: [2,3].

Key Points

1. Tree Definition: Connected and acyclic; the extra edge is the one that closes a cycle
2. Cycle Detection: Union-Find reports the edge whose endpoints are already connected
3. Order Guarantee: Scanning in input order naturally returns the answer that occurs last
4. Undirected Graph: The edge direction is irrelevant; only connectivity matters
5. Node Labels: Nodes are 1-indexed, so the parent array is sized n + 1