Redundant Connection

union-findgraphcycle-detection

Problem

You have a graph of n nodes labeled 1 to n, described by edges where edges[i] = [ai, bi] indicates an edge between nodes ai and bi. The graph started as a tree with n nodes and one additional edge was added, creating exactly one cycle. Return the edge that, if removed, would make the graph a tree again — if multiple answers exist, return the one that occurs LAST in the input.

Examples

Example 1

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

Output: [2,3]

Explanation: Removing [2,3] breaks the cycle 1-2-3-1; it's the last edge that creates the cycle.

Example 2

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

Output: [1,4]

Explanation: The cycle is 1-2-3-4-1; [1,4] is the last edge processed that connects two already-connected nodes.

Constraints

•n == edges.length
•3 <= n <= 1000
•edges[i].length == 2
•1 <= ai < bi <= edges.length
•ai != bi
•No repeated edges

Hints

Hint 1

Process edges in order, using Union-Find: for each edge, if the two nodes are ALREADY in the same component, this edge is the redundant one.

Hint 2

Union by rank/size and path compression keep find() close to O(1) amortized, so the whole scan is close to O(n).

Solutions

class UnionFind {
    int[] parent, rank;
    UnionFind(int n) {
        parent = new int[n + 1];
        rank = new int[n + 1];
        for (int i = 0; i <= n; i++) parent[i] = i;
    }
    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]); // path compression
        return parent[x];
    }
    boolean union(int x, int y) {
        int rx = find(x), ry = find(y);
        if (rx == ry) return false; // already connected -> this edge is redundant
        if (rank[rx] < rank[ry]) { int t = rx; rx = ry; ry = t; }
        parent[ry] = rx;
        if (rank[rx] == rank[ry]) rank[rx]++;
        return true;
    }
}

public int[] findRedundantConnection(int[][] edges) {
    UnionFind uf = new UnionFind(edges.length);
    for (int[] edge : edges) {
        if (!uf.union(edge[0], edge[1])) return edge; // first edge that connects an already-joined pair
    }
    return new int[0];
}

Time: O(n α(n)) — near-linear, α is the inverse Ackermann function · Space: O(n)