Redundant connection

A tree got one extra edge, which created exactly one cycle. Find that edge: the first one whose two ends are already connected.

The idea

Add the edges one by one, in the given order. While an edge joins two different components it is a tree edge. The first edge whose two ends already share a root would connect two nodes that a path already links, so it closes a cycle. There is only one cycle, and this edge comes last among its edges in the input, which is exactly the one the problem asks to remove.

Code

public int[] FindRedundantConnection(int[][] edges) {
    int n = edges.Length;
    var parent = new int[n + 1];
    var rank = new int[n + 1];
    for (int i = 1; i <= n; i++) parent[i] = i;
    foreach (var e in edges) {
        int ra = Find(parent, e[0]), rb = Find(parent, e[1]);
        if (ra == rb) return e; // ends already connected: this edge closes the cycle
        if (rank[ra] < rank[rb]) (ra, rb) = (rb, ra);
        parent[rb] = ra;
        if (rank[ra] == rank[rb]) rank[ra]++;
    }
    return Array.Empty<int>();
}

static int Find(int[] parent, int x) {
    if (parent[x] != x)
        parent[x] = Find(parent, parent[x]); // path compression: point x straight at its root
    return parent[x];
}

Tips

• The input always has n edges on n nodes and is connected: a tree (n - 1 edges) plus one extra.
• Any edge on the cycle could be removed; the problem wants the one appearing last in the input, and processing in order finds precisely that one.
• Try "1 2, 1 3, 2 3": the cycle closes on the third edge, so the answer is [2, 3].

In the .NET library

Returning the int[] e itself is fine here: LeetCode compares the contents, and the caller gets the original pair.