intermediate8 min read·Updated October 2, 2026

Union-Find Redundant Connection Explained: Tracing Edges on [[1,2],[1,3],[2,3]]

Master Union-Find cycle detection with a step-by-step walkthrough of [[1,2],[1,3],[2,3]]. Build a mental model of disjoint sets and component leaders.

By Learnisim AI·Published October 2, 2026
LEARNING ARCSetup → Model in the example → Full trace → Twist → Edge cases → Apply
PREREQUISITES
  • Basic graph terminology (nodes, edges, undirected graphs)
  • Familiarity with arrays and recursion or iterative loops
Union-Find Redundant Connection: Edge Stream [[1,2], [1,3], [2,3]] 1. The Triangle Graph [1,2] [1,3] [2,3] REDUNDANT! 1 2 3 2. Forest Evolution (Parent Array: [0, 1, 2, 3]) Step 1: Edge [1, 2] roots: find(1)=1, find(2)=2 roots differ (1 != 2) parent[2] = 1 Step 2: Edge [1, 3] roots: find(1)=1, find(3)=3 roots differ (1 != 3) parent[3] = 1 Step 3: Edge [2, 3] find(2) -> 1 find(3) -> 1 root(2) == root(3)! Final Tree Representation 1 [Root Leader] 2 3 parent = [0, 1, 1, 1] Nodes 2 & 3 both point to root 1 Why Union-Find? O(1) amortized path lookups Avoids expensive BFS/DFS Instantly catches cycles when find(u) == find(v) Key Takeaways 1. Return the LAST extra edge that completes the cycle ([2,3]) 2. Order matters in streams Process edges sequentially Output: [2, 3]
Extra edge in [[1,2],[1,3],[2,3]] overview diagram
Why

Why We Need Union-Find to Catch Extra Edges

Phase 1: The Redundant Connection Problem

Imagine a network of computers where cables are plugged in one by one in a strict sequence: first between node 1 and node 2, then between node 1 and node 3, and finally between node 2 and node 3. This sequence is our locked example: edges added in order , , and on nodes.
As the final edge arrives, notice something crucial: nodes 2 and 3 are already indirectly connected through node 1 via the first two edges. Adding a direct cable between them creates a closed loop, or cycle. In graph problems, this final edge is redundant because a path between those two nodes already exists.
If we had to run a full breadth-first search or depth-first search traversal every time a new edge arrives to check if both endpoints can already reach each other, the algorithm would quickly grind to a halt on large graphs. We need a lightweight way to track connected components dynamically and instantly spot when two already-connected nodes are about to form a redundant link.
Why We Need Union-Find to Catch Extra Edges Sequence: [1,2] → [1,3] → [2,3] on 3 nodes Edge 1: [1, 2] 1 2 Connects 1 & 2 Edge 2: [1, 3] 1 2 3 Component: {1, 2, 3} Edge 3: [2, 3]! X 1 2 3 Redundant! Forms Cycle Why Naive Search Fails BFS / DFS Traversal on Every Edge O(V + E) The Performance Bottleneck Checking reachability by traversing the whole graph for every new cable quickly grinds to a halt! The Union-Find Superpower 1 Find(2) and Find(3) return same root (1) 2 Already connected! Instant cycle detection Time Complexity: Nearly O(1) per edge!
Why We Need Union-Find to Catch Extra Edges diagram
Model

The Forest of Disjoint Sets and Component Leaders

Phase 2: The Forest of Disjoint Sets

To catch when an edge forms a cycle in our graph with and edges , we need a data structure that tracks which nodes belong to the same connected group. Instead of running a fresh breadth-first search or depth-first search every time an edge arrives, we model the graph as a forest (a collection of trees). Each tree represents a connected component, and every component elects a single root leader (or representative).
In our working example, we maintain a parent array or lookup table. Initially, every node is isolated in its own set, meaning each node is its own parent: node 1 points to 1, node 2 points to 2, and node 3 points to 3. When we process an edge like , we do not care about the physical geometry of the path; we only ask: Does node 1 and node 2 share the same root leader? If their roots differ, they live in separate components, so we merge their trees by pointing one root to the other. If their roots are already identical, they are already connected, revealing that the incoming edge is completely redundant.
python
# Conceptual root lookup for our n=3 nodes
parent = {1: 1, 2: 2, 3: 3}
When we evaluate the edge later in the sequence, our mental model relies entirely on walking up the parent chain from each endpoint until we find the ultimate root. If the root of 2 matches the root of 3, we have found our redundant connection.
python
parent = {1: 1, 2: 2, 3: 3}
# Given the initial parent dictionary above,
# what is the root leader of node 2 before any edges are processed?
Union-Find Forest: Detecting Redundant Edge [2,3] Edges = [[1,2], [1,3], [2,3]] | Root lookup reveals shared component leader 1. Isolated Forest (Init) parent = {1:1, 2:2, 3:3} 1 → 1 2 → 2 3 → 3 Each node is its own root • Edge [1,2] merges 1 & 2 • Edge [1,3] merges 1 & 3 • Edge [2,3] tests roots... 2. Merged Component Root leader of all is Node 1 1 (Root Leader) 2 3 Parent Map Lookup find(2) walks up → Root 1 find(3) walks up → Root 1 Roots Match! Cycle Found. 3. Redundant Edge Incoming Edge: [2, 3] Root of Node 2 Leader = 1 Root of Node 3 Leader = 1 RESULT: Roots are identical! Both 2 and 3 already belong to Tree 1. Discard Edge [2,3]
The Forest of Disjoint Sets and Component Leaders diagram
Worked example

Tracing Union-Find on [[1, 2], [1, 3], [2, 3]] Step by Step

Phase 3: Working Through the Triangle Edge by Edge

To see how the parent array tracks connected components, let us process our locked example: an undirected graph with nodes and the edge stream [[1, 2], [1, 3], [2, 3]]. We initialize a Disjoint Set Union (DSU) parent array where each node starts as its own root: parent = [0, 1, 2, 3] (using 1-indexed nodes).

Given

- Nodes:
- Edge list: [[1, 2], [1, 3], [2, 3]]
- Initial parent array: parent = [0, 1, 2, 3]

Steps

1. Process Edge [1, 2]:
- Find root of node 1: find(1) returns 1.
- Find root of node 2: find(2) returns 2.
- Since roots differ (), we union them. Let us set parent[2] = 1.
- Parent array updates to: [0, 1, 1, 3].
2. Process Edge [1, 3]:
- Find root of node 1: find(1) returns 1.
- Find root of node 3: find(3) returns 3.
- Since roots differ (), we union them. Let us set parent[3] = 1.
- Parent array updates to: [0, 1, 1, 1].
3. Process Edge [2, 3]:
- Find root of node 2: find(2) follows parent[2] == 1, returning root 1.
- Find root of node 3: find(3) follows parent[3] == 1, returning root 1.
- Both nodes share the exact same root (). A connection already exists between them!

Result

- Edge [2, 3] is identified as the redundant connection and returned immediately.
python
def find(parent, i):
    if parent[i] == i:
        return i
    parent[i] = find(parent, parent[i])
    return parent[i]

# Given the final parent array state [0, 1, 1, 1] after processing [1, 2] and [1, 3],
# trace what find(2) and find(3) return when evaluating the edge [2, 3].
Phase 3: Processing Triangle Edges & Finding Redundancy Edge stream: [[1, 2], [1, 3], [2, 3]] | Parent State after first two edges: [0, 1, 1, 1] Graph & Union-Find Forest [1, 2] merged [1, 3] merged [2, 3] redundant! 1 Root (leader) 2 3 Evaluating Edge [2, 3] 1. find(2): Follows parent[2] == 1 Returns root = 1 2. find(3): Follows parent[3] == 1 Returns root = 1 3. Compare Roots: Root(2) == Root(3) (1 == 1) Both nodes already belong to the exact same component!
Tracing Union-Find on [[1, 2], [1, 3], [2, 3]] Step by Step diagram
Practice

Put Your DSU Skills to Work on a Modified Edge List

Phase 4: Practice

Now it is your turn to trace how Disjoint Set Union handles a modified stream of connections. Imagine we take our familiar node network, but change the arrival order and add one new edge to the sequence: [[1, 3], [2, 3], [1, 2]].

The Task

Starting with a fresh 1-indexed parent array where parent = [0, 1, 2, 3], simulate the algorithm edge by edge:
1. Process edge [1, 3]
2. Process edge [2, 3]
3. Process edge [1, 2]
Determine which edge triggers find(u) == find(v) first, marking it as redundant.

Self-Check Questions

•What is the parent array state immediately after processing the first two edges?

* Which specific root leaders are compared when the algorithm evaluates the final edge [1, 2]?
•Does changing the arrival order alter the final connected component structure before the redundant edge appears?
python
def find(parent, i):
    if parent[i] == i:
        return i
    parent[i] = find(parent, parent[i])
    return parent[i]

# Try tracing edges: [[1, 3], [2, 3], [1, 2]]
# parent = [0, 1, 2, 3]
Apply

Applying Union-Find Beyond Basic Cycle Detection

Phase 5: Transfer

Now that you have traced the DSU algorithm on the edge list [[1,2], [1,3], [2,3]] and pinpointed [2,3] as the redundant connection, let us look at how this exact same pattern solves problems outside of raw graph networks.
Consider a financial fraud detection system where incoming transactions link accounts together: account 1 transfers to account 2, then 1 to 3, and finally 2 to 3. Just like our graph edges, if a new transaction arrives between two accounts that already share a common cluster root, it forms a closed loop of money movement that warrants closer inspection.
The mechanics remain identical to our DSU model:
- Nodes Bank accounts
- Edges Transactions between accounts
- Cycle detection Identifying a redundant transaction that forms a closed loop among already-linked entities
python
# Same find and union logic applied to account clusters
parent = {1: 1, 2: 1, 3: 1}
# A transaction between 2 and 3 triggers find(2) == find(3) == 1 -> Redundant!
By leveraging path compression and union by rank, this transfer domain handles millions of dynamic events in nearly constant time per operation.
python
def find_redundant_transaction(edges):
    # Apply your DSU template to find the first redundant edge
    pass

FAQ

Why is [2, 3] the redundant connection in the example [[1, 2], [1, 3], [2, 3]]?
Nodes 1, 2, and 3 are already in the same connected component after processing [1, 2] and [1, 3]. When edge [2, 3] is evaluated, both 2 and 3 share the same root leader, revealing that adding this edge creates a cycle.
What is the time complexity of using Union-Find to detect a redundant connection?
With path compression and union by rank/size optimizations, the time complexity is nearly O(N) for N edges, operating in almost constant time O(α(N)) per operation.
Can Union-Find detect cycles in directed graphs?
Standard Disjoint Set Union (DSU) is designed for undirected graphs. Detecting cycles in directed graphs typically requires Depth First Search (DFS), Breadth First Search (BFS), or Kahn's algorithm for topological sorting.

Keep learning