Redundant Connection

1. Problem & Core Objective

You start with a tree on n nodes (labelled 1 to n) and one extra edge is added, creating exactly one cycle. Return the edge that can be removed to restore a tree. If several answers exist, return the one that appears last in the input.

edges = [[1,2],[1,3],[2,3]]        →  [2,3]
edges = [[1,2],[2,3],[3,4],[1,4],[1,5]]  →  [1,4]

Constraints: 3 <= n <= 1000 · exactly n edges · no self-loops, no duplicate edges · the input is always a tree plus one edge

What's actually being tested: that union-find finds the redundant edge directly — and, subtly, that processing edges in order automatically satisfies the "last one" tie-break. The tie-break looks like an extra requirement and turns out to be free.

2. First-Principles Thought Process

What "redundant" means

The graph has n nodes and n edges. A tree has n − 1, so exactly one edge is surplus, and it creates exactly one cycle.

Any edge on that cycle could be removed to restore a tree — removing a cycle edge leaves the two endpoints still connected via the rest of the cycle. So there may be several valid answers.

Union-find finds it with no extra machinery

Process edges in input order. For each (u, v):

• if find(u) != find(v) — they were in different components, so this edge is necessary; union them
• if find(u) == find(v) — they were already connected, so a path already exists and this edge closes a cycle

That's the same test as Graph Valid Tree, where it meant "reject". Here it means "this is the answer".

Why processing in order gives the "last" edge for free

The problem asks for the edge appearing last in the input among the valid answers. That sounds like it needs a scan of all candidates.

It doesn't. Because there is exactly one cycle, the first edge that closes it is the last edge of that cycle to be processed — every earlier cycle edge was still connecting distinct components at the time it was seen.

So the first find(u) == find(v) encountered, scanning left to right, is the last cycle edge in input order. Return it immediately.

That equivalence depends on there being exactly one cycle, which the constraints guarantee. With two cycles the argument breaks, and I'd state that rather than present the shortcut as general.

Why not DFS

You could find the cycle by DFS and then pick the latest-indexed edge on it. That works, but it's two phases — locate the cycle, then search it — where union-find answers in one pass.

3. Solution Paths

Approach 1 — Remove each edge and test (brute force)

public int[] findRedundantConnection(int[][] edges) {
    for (int i = edges.length - 1; i >= 0; i--) {          // last first
        if (isTreeWithout(edges, i)) return edges[i];
    }
    return new int[0];
}

private boolean isTreeWithout(int[][] edges, int skip) {
    int n = edges.length;                                   // n nodes, n edges
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i <= n; i++) adj.add(new ArrayList<>());
    for (int i = 0; i < edges.length; i++) {
        if (i == skip) continue;
        adj.get(edges[i][0]).add(edges[i][1]);
        adj.get(edges[i][1]).add(edges[i][0]);
    }
    boolean[] seen = new boolean[n + 1];
    dfs(adj, 1, seen);
    for (int i = 1; i <= n; i++) if (!seen[i]) return false;   // disconnected
    return true;                                                // n-1 edges + connected = tree
}

• Time O(n · (V + E)) = O(n²) · Space O(V + E) rebuilt each time

Counter-questions on this approach

⭐ "Why does checking connectivity suffice, without a cycle check?"

Because removing one edge from n leaves n − 1, and with exactly n − 1 edges connected and acyclic are equivalent — the theorem from question 10. So verifying connectivity proves it's a tree.

That's a legitimate use of the shortcut, even in a solution I'd reject for other reasons.

⭐ "Why iterate from the last edge backwards?"

To satisfy the tie-break directly — the first valid removal found scanning backwards is the last valid one in input order.

It works, but it costs a full graph rebuild and traversal per candidate. Union-find gets the same answer in one forward pass, because the first cycle-closing edge is the last cycle edge.

"Is O(n²) a problem at n = 1000?"

10^6 operations — it would pass. The objection is that it rebuilds the adjacency list n times and re-traverses, when the structure needed is a single int[n+1].

Approach 2 — Union-Find, return the first edge that closes a cycle (optimal)

public int[] findRedundantConnection(int[][] edges) {
    int n = edges.length;                       // n nodes, labelled 1..n
    int[] parent = new int[n + 1];
    int[] size = new int[n + 1];
    for (int i = 1; i <= n; i++) { parent[i] = i; size[i] = 1; }

    for (int[] e : edges) {                     // input order matters
        int a = find(parent, e[0]), b = find(parent, e[1]);
        if (a == b) return e;                   // already connected — this edge is redundant

        if (size[a] < size[b]) { int t = a; a = b; b = t; }
        parent[b] = a;
        size[a] += size[b];
    }
    return new int[0];                          // unreachable given the constraints
}

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

Trace — edges = [[1,2],[2,3],[3,4],[1,4],[1,5]]:

• Time O(n · α(n)) — effectively linear · Space O(n)

Counter-questions on this approach

⭐ "Why does the FIRST cycle-closing edge satisfy 'return the last valid answer'?"

Because there is exactly one cycle. Every edge on that cycle except the last one to be processed was, at the time it was seen, still joining two distinct components — so none of them triggered find(u) == find(v).

Only when the final cycle edge arrives are both endpoints already connected. So the first edge that closes a cycle is, necessarily, the last cycle edge in input order — which is exactly the tie-break the problem wants.

The requirement that looked like extra work is satisfied for free by scanning left to right.

⭐ "Does that argument survive two cycles?"

No, and it's worth stating the limit. With two independent cycles, the first cycle-closing edge belongs to whichever cycle completes first, which needn't be the globally last valid edge.

The constraints guarantee exactly one extra edge and therefore exactly one cycle, so the shortcut is sound here — but I'd present it as depending on that guarantee rather than as a general property.

⭐ "Why is find(u) == find(v) the definition of redundant?"

Because they're already in the same component, so a path between them exists. Adding this edge creates a second path, and two distinct paths between the same pair is precisely a cycle.

Removing this edge leaves the original path intact, so connectivity is preserved — which is what makes it safe to remove.

"Why size n + 1?"

Nodes are labelled 1 to n, not 0 to n − 1. Sizing the array n and indexing with node labels would throw on node n.

And n equals edges.length here, because the graph has exactly as many edges as nodes — worth noting, since n isn't passed as a parameter.

"Why does the edge count equal the node count?"

A tree on n nodes has n − 1 edges; adding one gives n. So edges.length == n, which is how the node count is recovered from the input.

"Could the loop finish without returning?"

Not with valid input — the extra edge guarantees a cycle exists. The return new int[0] is unreachable and documents the precondition rather than handling a real case.

Approach 3 — DFS to find the cycle

Build the graph, find the cycle by DFS, then return the edge on it with the largest input index.

• Time O(V + E) · Space O(V + E)

Counter-questions on this approach

⭐ "Same complexity. Why prefer union-find?"

It's two phases: locate the cycle, then scan its edges for the latest index. Union-find does it in one pass and needs no adjacency list — just int[n+1].

The DFS also needs the parent check for undirected edges, and then extra bookkeeping to recover which edges lie on the cycle rather than just which nodes.

"When would DFS be the better tool?"

If you needed the cycle itself — its length, its members, or all edges on it. Union-find tells you which edge closes a cycle but not what the cycle contains. Recovering that needs a separate traversal anyway.

"What about the harder variant, LeetCode 685?"

Redundant Connection II is the directed version, and it genuinely needs more care: a node may have two parents, or there may be a cycle, or both. Union-find alone isn't sufficient — you have to identify candidate edges first and test them. Worth naming as substantially harder rather than a small variation.

Comparison

4. Why the Optimal Wins

The brute force rebuilds the graph and re-traverses once per candidate edge. The DFS version finds the cycle and then searches it.

Union-find answers in one forward pass over the edges, with a single int[n+1] and no adjacency list. And the tie-break — "return the last valid edge" — which looks like it needs comparing candidates, falls out of the scan order because with exactly one cycle, the first edge to close it is the last edge of that cycle.

The framing worth keeping:

find(u) == find(v) means a path already exists, so this edge closes a cycle. Scanning in input order, the first such edge is the last edge of the cycle — which is exactly the tie-break, for free. That equivalence needs there to be only one cycle.

5. Java Prerequisites

1-indexed union-find

int[] parent = new int[n + 1];                 // nodes are 1..n
for (int i = 1; i <= n; i++) parent[i] = i;

Sizing n instead of n + 1 throws on the highest-numbered node.

Recovering n from the input — edges.length == n, since a tree plus one edge has as many edges as nodes.

The redundancy test

if (find(e[0]) == find(e[1])) return e;        // already connected

Return the array itself — return e; returns the caller's int[], which is fine since it isn't mutated. new int[]{e[0], e[1]} if a defensive copy is wanted.

6. Interview Communication Guide

Clarifying questions: Is the input guaranteed to be a tree plus exactly one edge (yes — this is what makes the shortcut valid)? Are nodes 1-indexed (yes)? Which answer if several are valid (the last in input order)? Are edges directed (no — LC 685 is the directed version and is much harder)?

The pitch

"There are n nodes and n edges, so exactly one edge is surplus and it creates exactly one cycle. Any edge on that cycle could be removed, since the endpoints would still be connected via the rest of the cycle — so there may be several valid answers.

Union-find finds it in one pass. Process the edges in input order; for each one, check whether its endpoints are already in the same component. If they are, a path between them already exists, so this edge creates a second path — that's a cycle, and this edge is the redundant one.

That's the same test as Graph Valid Tree, where it meant 'reject'. Here it means 'this is the answer'.

The interesting part is the tie-break. The problem wants the last valid edge in input order, which sounds like it needs comparing candidates. It doesn't. Because there's exactly one cycle, every cycle edge except the final one was still joining two distinct components when it was processed — so none of them triggered the check. Only the last one finds both endpoints already connected.

So the first cycle-closing edge, scanning left to right, is the last cycle edge. Return it immediately.

I'd flag that this depends on there being exactly one cycle. With two, the first closure belongs to whichever cycle completes first, which needn't be the globally last valid edge. The constraints guarantee one, so it's sound here.

O(n · α(n)) with path compression and union by size, O(n) space, no adjacency list.

One detail: nodes are labelled 1 to n, so the parent array needs size n + 1. And n isn't given — it equals edges.length, because a tree plus one edge has as many edges as nodes."

Edge cases to volunteer:

Name the second row. The redundant edge is [1,4], not the final input edge [1,5] — so a solution that just returns the last edge, or scans backwards for any cycle edge, gets it wrong.

7. Follow-Up Questions — Modified Constraints

⭐ "What if the graph were DIRECTED?"

LeetCode 685, and genuinely harder. Three cases: a node has two parents, there's a cycle, or both. Union-find alone can't distinguish them — you first identify the candidate edges (the two entering a two-parent node), then test whether removing each restores a valid rooted tree. Worth naming as a different algorithm rather than a tweak.

⭐ "What if more than one edge were redundant?"

Return every edge that closes a cycle — all of them, rather than returning on the first. But the "last in input order" reasoning breaks, as discussed, so the tie-break would need explicit handling.

"Return the cycle itself, not just the redundant edge."

Union-find doesn't give it. After finding the closing edge (u, v), run a DFS or BFS from u to v in the graph without that edge — the path found plus the edge is the cycle. O(V + E).

"What if edges could be removed as well as added?"

Union-find has no undo, so it can't handle deletion. You'd need a link-cut tree for O(log n) dynamic connectivity, or process the queries offline in reverse so deletions become additions.

"What if n were 10^5?"

Union-find scales fine — int[10^5] is 400 KB. I'd make find iterative to avoid deep recursion if union by size were omitted. The remove-and-test brute force would be 10^10 and completely infeasible.

"Find the edge whose removal minimises the largest remaining component."

A different question — that's about bridges and component sizes, solved with Tarjan's bridge-finding algorithm plus subtree sizes, at O(V + E). Union-find doesn't answer it, because it has no notion of which edges are critical.