Definition
- Tree plus one edge – the input is a tree with n nodes that had exactly one extra edge added, creating exactly one cycle.
- Union-Find – a data structure that tracks connected components;
find(x)returns the root of x's component, andunion(x, y)merges two components. - Redundant edge detection – for each edge, check if both endpoints already share a root before unioning; if they do, that edge closes a cycle.
- Input order – since the problem asks for the last redundant edge in input order and there is exactly one cycle, the first detected edge during a forward scan is the answer.
- Path compression and union by rank – optimisations that make Union-Find operations nearly constant time.
At the National Bank of India, the inter-branch settlement network is supposed to be a loop-free tree so each settlement message travels one unique path. Someone accidentally added an extra cable, creating a loop that causes duplicate messages. Rajesh lays cables one by one; the cable that connects two branches already reachable from each other is the redundant one, and he flags it for removal.
Understanding the Concepts
What is the Redundant Connection problem?
The problem gives a graph that was originally a tree of n nodes (connected, no cycles) with exactly one extra edge added, creating a single cycle. The task is to find and return that extra edge. If there are multiple candidates, return the last one in input order.
package com.bank.service;
public class RedundantConnection {
private int[] parent;
private int[] rank;
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 u = edge[0], v = edge[1];
if (find(u) == find(v)) return edge; // cycle detected
union(u, v);
}
return new int[0]; // should not reach here
}
private int find(int x) {
if (parent[x] != x) parent[x] = find(parent[x]); // path compression
return parent[x];
}
private void union(int a, int b) {
int ra = find(a), rb = find(b);
if (ra == rb) return;
if (rank[ra] < rank[rb]) parent[ra] = rb;
else if (rank[ra] > rank[rb]) parent[rb] = ra;
else { parent[rb] = ra; rank[ra]++; }
}
public static void main(String[] args) {
int[][] edges = {{1, 2}, {1, 3}, {2, 3}};
int[] result = new RedundantConnection().findRedundantConnection(edges);
System.out.println("Redundant edge: [" + result[0] + ", " + result[1] + "]");
}
}
Redundant edge: [2, 3]
Why does Union-Find detect the redundant edge?
Union-Find tracks which nodes are in the same connected component. For each edge, we check whether both endpoints already belong to the same component by comparing their roots. If they do, adding this edge would create a cycle because a path already exists between them. If they do not, we union them. The first edge that fails the union check is the one that closes the cycle.
package com.bank.service;
public class WhyUnionFind {
// Edge processing in order: {1,2}, {1,3}, {2,3}
//
// After {1,2}: components {1,2} and {3}
// After {1,3}: components {1,2,3}
// Edge {2,3}: find(2)==find(3) => already connected => REDUNDANT
public static void main(String[] args) {
System.out.println("Union-Find detects the edge that closes a cycle.");
System.out.println("If find(u) == find(v) before union, the edge is redundant.");
}
}
How do path compression and union by rank work?
Path compression flattens the tree during find operations by making every node point directly to the root. Union by rank always attaches the shorter tree under the taller one. Together they make each operation nearly O(1), specifically O(alpha(n)) where alpha is the inverse Ackermann function.
package com.bank.service;
public class PathCompressionDemo {
// Without path compression: find can be O(n) in a degenerate chain
// With path compression: find flattens the tree, subsequent finds are O(1)
// Without union by rank: tree can degenerate into a linked list
// With union by rank: tree stays balanced, height stays O(log n)
static int[] parent = {0, 1, 2, 3, 4, 5};
static int find(int x) {
if (parent[x] != x) parent[x] = find(parent[x]); // path compression
return parent[x];
}
public static void main(String[] args) {
// Chain: 5 -> 4 -> 3 -> 2 -> 1
parent[5] = 4; parent[4] = 3; parent[3] = 2; parent[2] = 1;
System.out.println("Before: parent[5]=" + parent[5]);
System.out.println("find(5) = " + find(5));
System.out.println("After compression: parent[5]=" + parent[5]); // now points to 1
}
}
Before: parent[5]=4
find(5) = 1
After compression: parent[5]=1
How is this different from cycle detection with DFS?
| Feature | Union-Find | DFS cycle detection |
|---|---|---|
| Edge processing | one edge at a time, incremental | full graph traversal |
| Data structure | parent array + rank array | adjacency list + visited set |
| Returns | the specific edge causing the cycle | whether a cycle exists (boolean) |
| Time | O(E * alpha(V)) near-linear | O(V + E) |
| Best for | incremental edge addition | static graph |
package com.bank.service;
public class UnionFindVsDFS {
public static void main(String[] args) {
System.out.println("Union-Find: processes edges incrementally, returns the edge.");
System.out.println("DFS: traverses full graph, returns boolean.");
System.out.println("For this problem, Union-Find is the right choice.");
}
}
What are the edge cases?
Edge cases include a graph with only two nodes and two edges between them (the second edge is redundant), a graph where the redundant edge is the very first edge (a self-loop, though the problem typically excludes self-loops), and a graph where the cycle involves all n nodes.
package com.bank.service;
public class RedundantEdgeCases {
public static void main(String[] args) {
RedundantConnection solver = new RedundantConnection();
// Two nodes, two edges: second is redundant
int[][] twoNodes = {{1, 2}, {2, 1}};
int[] r = solver.findRedundantConnection(twoNodes);
System.out.println("Two nodes: [" + r[0] + ", " + r[1] + "]");
// Cycle involving all nodes
int[][] fullCycle = {{1, 2}, {2, 3}, {3, 4}, {4, 1}};
r = new RedundantConnection().findRedundantConnection(fullCycle);
System.out.println("Full cycle: [" + r[0] + ", " + r[1] + "]");
}
}
Two nodes: [2, 1]
Full cycle: [4, 1]
What are common mistakes?
The most common mistake is forgetting to initialise each node's parent to itself. Without initialisation, all parents default to 0, and find incorrectly treats all nodes as connected. Another mistake is not implementing path compression, which makes find O(n) in the worst case.
Wrong code:
// WRONG: parent array not initialised
int[] parent = new int[n + 1]; // all zeros by default
// find(1) returns 0, find(2) returns 0 => looks like they share a root
Correct code:
// CORRECT: initialise each node as its own parent
for (int i = 1; i <= n; i++) parent[i] = i;
// find(1) returns 1, find(2) returns 2 => correctly separate
When should you use Union-Find for cycle detection?
Use Union-Find for cycle detection when edges are processed incrementally and you need to identify the specific edge that creates a cycle. It is also the right tool when you need to count connected components as edges are added. For a static graph where you only need a boolean answer, DFS is simpler.
package com.bank.service;
public class WhenToUseUnionFind {
public static void main(String[] args) {
System.out.println("Use Union-Find when:");
System.out.println(" 1. Edges arrive incrementally.");
System.out.println(" 2. Need the specific cycle-causing edge.");
System.out.println(" 3. Need connected component count over time.");
System.out.println("Use DFS when:");
System.out.println(" 1. Graph is static.");
System.out.println(" 2. Only need boolean cycle detection.");
}
}
What should a senior engineer know?
A senior engineer knows that this problem generalises to incremental cycle detection in any undirected graph, not just trees. They also know that the directed variant (Redundant Connection II) is significantly harder because it requires tracking in-degree-two conflicts and handling both cycles and multiple-parent nodes. In production at National Bank of India, the settlement topology validator uses Union-Find to check that each new link does not create a loop in the settlement tree.
package com.bank.service;
public class SeniorRedundantNotes {
public static void main(String[] args) {
System.out.println("Senior insights:");
System.out.println(" 1. Generalises to any undirected incremental cycle detection.");
System.out.println(" 2. Directed variant (II) tracks in-degree-two + cycles.");
System.out.println(" 3. Union-Find with path compression + rank: O(E * alpha(V)).");
System.out.println(" 4. Production use: settlement topology validation.");
}
}
Visual Overview
Redundant Connection: Union-Find Processing
Edges: {1,2}, {1,3}, {2,3}
Step 1: edge {1,2}
┌───┐ ┌───┐ ┌───┐
│ 1 │───│ 2 │ │ 3 │ find(1)=1, find(2)=2, different => union
└───┘ └───┘ └───┘
Step 2: edge {1,3}
┌───┐ ┌───┐ ┌───┐
│ 1 │───│ 2 │ │ 3 │ find(1)=1, find(3)=3, different => union
└─┬─┘ └───┘ └───┘
│
┌─▼─┐
│ 3 │
└───┘
Step 3: edge {2,3}
find(2) = 1, find(3) = 1 => SAME ROOT => CYCLE!
Return {2, 3} as the redundant edge.
Union-Find Parent Array:
┌─────┬───┬───┬───┐
│ idx │ 1 │ 2 │ 3 │
├─────┼───┼───┼───┤
│ par │ 1 │ 1 │ 1 │ all point to root 1
└─────┴───┴───┴───┘
Key Takeaway
Redundant Connection is a textbook application of Union-Find for cycle detection. The graph started as a tree and had exactly one extra edge added, creating a single cycle. By processing edges in input order and checking whether both endpoints already share a root before unioning them, the first edge that fails the check is the one that closes the cycle.
The Union-Find data structure tracks connected components using a parent array. Path compression flattens the tree during find operations, and union by rank keeps the tree balanced. Together they make each operation nearly O(1), giving the entire algorithm O(E times alpha(V)) time where alpha is the inverse Ackermann function.
The key correctness detail is initialising each node's parent to itself. Without this, all parents default to 0 and find incorrectly treats all nodes as connected from the start. The problem asks for the last redundant edge in input order, and since there is exactly one cycle, the first detected edge during a forward scan is the correct answer.
At the National Bank of India, the inter-branch settlement topology was supposed to be a loop-free tree. A misconfiguration added one extra link that caused duplicate settlement messages to circulate. Rajesh used Union-Find to process links in the order they were configured and flagged the first link whose two branches were already reachable from each other. Removing that link restored the tree and stopped the duplicates.
Remember one sentence: process edges with Union-Find, and the first edge whose endpoints already share a root is the redundant one that closes the cycle.
---