DSA-110 · Find the last input occurrence whose endpoints were already connected
Redundant Connection
Core · Java 21 · Version 1 · editorial draft
Java reference and baseline verified on JDK 21: 17184 deterministic checks. Learner drafts are not executed.
Understand the problem
Return a fresh copy of the last cycle-closing undirected edge in input order, or a fresh empty array if no edge closes a cycle. On the standard tree-plus-one-edge case, this is the last removable edge on its unique cycle.
- edges is a nonnull array of two-int endpoint rows. Labels are positive integers 1..100000; empty input is valid. At most 200,000 occurrences is a size precondition. Null outer input throws NullPointerException; null/non-pair rows, nonpositive labels, and labels above 100000 throw IllegalArgumentException before processing any prefix.
- Let U be the maximum input label, or zero for empty input. The implementation allocates the full 1..U universe and translates endpoints to zero-based DSU indices. Sparse labels therefore still incur O(U) allocation. Self-loops, duplicate edges, reversed duplicates, disconnected graphs, and shared input row objects are supported.
- An occurrence is cycle-closing when its endpoints are connected by earlier occurrences; a self-loop qualifies immediately. Preserve the original orientation of the latest such pair and copy it into a fresh result independent of source rows and other calls. In a general multicycle stream, this result is not a promise that deleting one edge repairs the whole graph; that repair guarantee applies to the connected simple tree-plus-one-edge subset.
Examples
Input:
[[1,2],[1,3],[2,3]]
Output:[2,3]Before the last edge, 2 and 3 already connect through 1.
Input:
[[1,2],[2,3],[3,1],[3,4],[4,1]]
Output:[4,1]Two different occurrences close cycles. Return the later one without claiming a single deletion repairs both cycles.
Input:
[[2,1],[1,2]]
Output:[1,2]The second occurrence is redundant even though its orientation differs from the first.
Input:
[[7,7]]
Output:[7,7]A vertex is already connected to itself; a self-loop is a cycle-closing occurrence.
Before you start
- Undirected paths, cycles, and ordered edge prefixes
- Union-find membership tests and root attachment
Recognize the structure
Connectivity before each insertion answers whether the new undirected edge contributes a new link or closes an existing path. This is different from returning an arbitrary cycle vertex or a directed-cycle witness. Input order determines which redundant occurrence is last, and positive labels require an explicit indexing conversion.
Try before revealing
Hint 1
Before inserting an undirected edge, ask whether its endpoints are already connected.
Hint 2
A failed union records a cycle-closing occurrence; a successful union only joins components.
Hint 3
Keep the latest failed pair in a fresh array, preserving external labels and orientation.
Derive the solution
Reveal the baseline, optimized reasoning, and Java code
Search the earlier graph before every insertion
Maintain undirected adjacency lists for earlier occurrences. Before inserting (u,v), BFS from u and ask whether v is already reachable; u reaches itself immediately. If yes, copy this edge as the current answer, then insert it anyway. This compiling baseline handles the same general stream contract but repeats graph traversal for each occurrence.
Improve the baseline
Validate the full stream and label universe
Determine U only after validating each row and endpoint. Allocate U singleton DSU indices and map external label x to index x−1. Sparse IDs are not implicitly compressed.
Use failed union as a connectivity certificate
A successful union adds a link between separate components. A failed union means a previous path already joins the endpoints; record a fresh pair with the original labels and orientation.
Keep scanning after the first redundant edge
Overwrite the private candidate on every failed union. Returning at the first failure would violate the general latest-occurrence rule. The standard unicyclic subset has exactly one failure in stream order.
Why it is correct
Forest and size invariant
Every parent chain ends at a self-parent root. Roots partition vertices into disjoint sets; only a root’s size is its current component cardinality. Nonroot size entries remain stale. Union attaches one root to another, so no parent cycle is introduced.
Prefix connectivity detects a cycle-closing occurrence
Before each edge, DSU sets equal the connected components of the earlier graph. Equal roots mean a previous path plus this occurrence closes a cycle; different roots mean the new edge cannot yet close a cycle. Self-loops and parallel occurrences follow the same multigraph reasoning.
Last-occurrence and canonical repair guarantees
Overwriting only on failure preserves the invariant that the candidate is the latest redundant occurrence seen. For a connected simple graph that is a tree plus one edge, deleting any cycle edge leaves a tree. The last cycle edge in input order is the one whose endpoints first become connected before its own insertion, so the returned occurrence is the required last removable cycle edge.
Complete Java reference and baseline
Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.
import java.util.*;
public final class Solution {
private static final class Dsu {
final int[] parent,size;int components;
Dsu(int n){parent=new int[n];size=new int[n];components=n;for(int v=0;v<n;v++){parent[v]=v;size[v]=1;}}
int find(int v){while(v!=parent[v]){parent[v]=parent[parent[v]];v=parent[v];}return v;}
boolean union(int a,int b){int ra=find(a),rb=find(b);if(ra==rb)return false;if(size[ra]<size[rb]){int swap=ra;ra=rb;rb=swap;}parent[rb]=ra;size[ra]+=size[rb];components--;return true;}
}
private static int validate(int[][] edges) {
Objects.requireNonNull(edges,"edges");int maximum=0;for(int[] edge:edges){if(edge==null||edge.length!=2||edge[0]<1||edge[1]<1||edge[0]>100000||edge[1]>100000)throw new IllegalArgumentException("expected positive labels <=100000");maximum=Math.max(maximum,Math.max(edge[0],edge[1]));}return maximum;
}
public static int[] redundantEdge(int[][] edges) {
int maximum=validate(edges);Dsu dsu=new Dsu(maximum);int[] result=new int[0];
for(int[] edge:edges)if(!dsu.union(edge[0]-1,edge[1]-1))result=new int[]{edge[0],edge[1]};
return result;
}
public static int[] baseline(int[][] edges) {
int maximum=validate(edges);List<List<Integer>> graph=new ArrayList<>();for(int i=0;i<=maximum;i++)graph.add(new ArrayList<>());int[] result=new int[0];
for(int[] edge:edges){boolean[] seen=new boolean[maximum+1];ArrayDeque<Integer> queue=new ArrayDeque<>();seen[edge[0]]=true;queue.addLast(edge[0]);while(!queue.isEmpty()&&!seen[edge[1]]){int v=queue.removeFirst();for(int next:graph.get(v))if(!seen[next]){seen[next]=true;queue.addLast(next);}}if(seen[edge[1]])result=new int[]{edge[0],edge[1]};graph.get(edge[0]).add(edge[1]);graph.get(edge[1]).add(edge[0]);}return result;
}
}
Read the meaningful blocks
Iterative path halving is not full flattening
find rewrites the current vertex to its grandparent, then jumps to that updated parent. It may skip intermediate vertices and may leave a path of length greater than one. Rewiring preserves set membership; an unsuccessful union can still compress paths.
Copy an edge rather than returning its row
result=new int[]{edge[0],edge[1]} preserves orientation while preventing caller edits of the result from changing the source. Failed unions can compress parent links without changing component count.
A DSU forest is not a cycle witness
Attaching root rb to root ra may create a parent link that never appeared as an input edge. Recovering an actual earlier path needs separate graph/accepted-edge state.
Complexity
For E edge occurrences and U maximum label, main time is O(U+E·α(U+1)+1), with O(U+1) parent/size storage and O(1) returned pair storage. Candidate pairs may be allocated repeatedly, but only one current pair is live algorithmic output; cumulative allocations can be O(E). Sparse labels retain the U term.
The per-prefix BFS baseline takes O(U+E(U+E+1)+1) worst-case time and O(U+E+1) auxiliary adjacency/frontier storage. Main processing is iterative and supports a 100,000-label chain closed by one final edge. Union by size plus path halving gives inverse-Ackermann amortized operation cost over a sequence; it does not promise each individual find is constant time. A single find can still take O(log(U+1)) in a size-balanced forest. Parent links encode membership, not a path made of original graph edges.
Exact-state walkthroughs
Reveal normal and boundary traces
The last edge of a simple triangle closes the cycle
Input: [[1,2],[1,3],[2,3]] · Latest copied cycle-closing edge: [2,3]
Step 1 of 13: Initialize one singleton set for every vertex or account.
parent[v]=v and root size is one. Root IDs are implementation representatives, not necessarily the smallest member or an original graph edge.
Phase: initial.
Input undirected occurrences — exact order and orientation
- 0: (1, 2)
- 1: (1, 3)
- 2: (2, 3)
External labels are positive: label x uses DSU slot x−1. The allocated universe includes every label 1 through the maximum, even unobserved intermediate labels.
Parent forest — arrows are implementation links, not original graph edges
- label 1 (slot 0)parent → 1 (root)root size 1
- label 2 (slot 1)parent → 2 (root)root size 1
- label 3 (slot 2)parent → 3 (root)root size 1
Component count: 3. Root choices need not be the smallest member.
Current partition — members grouped by representative
- root 1: {1}
- root 2: {2}
- root 3: {3}
Latest copied redundant occurrence — original external labels
Empty.
A failed union certifies an earlier path (or a self-loop). The candidate updates in the separate record step. One-edge global repair is guaranteed only for the simple connected tree-plus-one-edge subset.
Exact arrays and equivalent static steps appear below. Logical partition/map views explain the Java implementation without adding those pictures to its workspace cost.
| Variable | Value |
|---|---|
| input | [[1,2],[1,3],[2,3]] |
| parent | [0,1,2] |
| size | [1,1,1] |
| components | 3 |
| processed | [] |
| phase | "initial" |
| current | null |
See the affected Java block
1 import java.util.*; 2 public final class Solution { 3 private static final class Dsu { 4 final int[] parent,size;int components; 5 Dsu(int n){parent=new int[n];size=new int[n];components=n;for(int v=0;v<n;v++){parent[v]=v;size[v]=1;}} 6 int find(int v){while(v!=parent[v]){parent[v]=parent[parent[v]];v=parent[v];}return v;} 7 boolean union(int a,int b){int ra=find(a),rb=find(b);if(ra==rb)return false;if(size[ra]<size[rb]){int swap=ra;ra=rb;rb=swap;}parent[rb]=ra;size[ra]+=size[rb];components--;return true;} 8 } 9 private static int validate(int[][] edges) { 10 Objects.requireNonNull(edges,"edges");int maximum=0;for(int[] edge:edges){if(edge==null||edge.length!=2||edge[0]<1||edge[1]<1||edge[0]>100000||edge[1]>100000)throw new IllegalArgumentException("expected positive labels <=100000");maximum=Math.max(maximum,Math.max(edge[0],edge[1]));}return maximum; 11 } 12 public static int[] redundantEdge(int[][] edges) { 13 int maximum=validate(edges);Dsu dsu=new Dsu(maximum);int[] result=new int[0]; 14 for(int[] edge:edges)if(!dsu.union(edge[0]-1,edge[1]-1))result=new int[]{edge[0],edge[1]}; 15 return result; 16 } 17 public static int[] baseline(int[][] edges) { 18 int maximum=validate(edges);List<List<Integer>> graph=new ArrayList<>();for(int i=0;i<=maximum;i++)graph.add(new ArrayList<>());int[] result=new int[0]; 19 for(int[] edge:edges){boolean[] seen=new boolean[maximum+1];ArrayDeque<Integer> queue=new ArrayDeque<>();seen[edge[0]]=true;queue.addLast(edge[0]);while(!queue.isEmpty()&&!seen[edge[1]]){int v=queue.removeFirst();for(int next:graph.get(v))if(!seen[next]){seen[next]=true;queue.addLast(next);}}if(seen[edge[1]])result=new int[]{edge[0],edge[1]};graph.get(edge[0]).add(edge[1]);graph.get(edge[1]).add(edge[0]);}return result; 20 } 21 } 22
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Initialize one singleton set for every vertex or account.
parent[v]=v and root size is one. Root IDs are implementation representatives, not necessarily the smallest member or an original graph edge.
- input
[[1,2],[1,3],[2,3]]- parent
[0,1,2]- size
[1,1,1]- components
3- processed
[]- phase
"initial"- current
null
- Find a representative with iterative path halving.
Each visited nonroot is rewired to its grandparent before jumping there. This can shorten paths without changing the partition; one halving find need not flatten every path completely.
- input
[[1,2],[1,3],[2,3]]- parent
[0,1,2]- size
[1,1,1]- components
3- processed
[]- index
0- edge
[1,2]- answer
[]- phase
"find"- current
0- role
"a"- path
[0]- changes
[]- root
0
- Find a representative with iterative path halving.
Each visited nonroot is rewired to its grandparent before jumping there. This can shorten paths without changing the partition; one halving find need not flatten every path completely.
- input
[[1,2],[1,3],[2,3]]- parent
[0,1,2]- size
[1,1,1]- components
3- processed
[]- index
0- edge
[1,2]- answer
[]- phase
"find"- current
1- role
"b"- path
[1]- changes
[]- root
1
- Join the smaller root tree under the larger one.
Equal root sizes retain the first root argument. Decrement component count only for a successful join; sizes at nonroots are stale and have no component-size meaning.
- input
[[1,2],[1,3],[2,3]]- parent
[0,0,2]- size
[2,1,1]- components
2- processed
[{"a":0,"b":1,"merged":true}]- index
0- edge
[1,2]- answer
[]- phase
"union"- current
0- rootA
0- rootB
1- kept
0- attached
1- merged
true
- Find a representative with iterative path halving.
Each visited nonroot is rewired to its grandparent before jumping there. This can shorten paths without changing the partition; one halving find need not flatten every path completely.
- input
[[1,2],[1,3],[2,3]]- parent
[0,0,2]- size
[2,1,1]- components
2- processed
[{"a":0,"b":1,"merged":true}]- index
1- edge
[1,3]- answer
[]- phase
"find"- current
0- role
"a"- path
[0]- changes
[]- root
0
- Find a representative with iterative path halving.
Each visited nonroot is rewired to its grandparent before jumping there. This can shorten paths without changing the partition; one halving find need not flatten every path completely.
- input
[[1,2],[1,3],[2,3]]- parent
[0,0,2]- size
[2,1,1]- components
2- processed
[{"a":0,"b":1,"merged":true}]- index
1- edge
[1,3]- answer
[]- phase
"find"- current
2- role
"b"- path
[2]- changes
[]- root
2
- Join the smaller root tree under the larger one.
Equal root sizes retain the first root argument. Decrement component count only for a successful join; sizes at nonroots are stale and have no component-size meaning.
- input
[[1,2],[1,3],[2,3]]- parent
[0,0,0]- size
[3,1,1]- components
1- processed
[{"a":0,"b":1,"merged":true},{"a":0,"b":2,"merged":true}]- index
1- edge
[1,3]- answer
[]- phase
"union"- current
0- rootA
0- rootB
2- kept
0- attached
2- merged
true
- Find a representative with iterative path halving.
Each visited nonroot is rewired to its grandparent before jumping there. This can shorten paths without changing the partition; one halving find need not flatten every path completely.
- input
[[1,2],[1,3],[2,3]]- parent
[0,0,0]- size
[3,1,1]- components
1- processed
[{"a":0,"b":1,"merged":true},{"a":0,"b":2,"merged":true}]- index
2- edge
[2,3]- answer
[]- phase
"find"- current
1- role
"a"- path
[1,0]- changes
[{"node":1,"before":0,"after":0}]- root
0
- Find a representative with iterative path halving.
Each visited nonroot is rewired to its grandparent before jumping there. This can shorten paths without changing the partition; one halving find need not flatten every path completely.
- input
[[1,2],[1,3],[2,3]]- parent
[0,0,0]- size
[3,1,1]- components
1- processed
[{"a":0,"b":1,"merged":true},{"a":0,"b":2,"merged":true}]- index
2- edge
[2,3]- answer
[]- phase
"find"- current
2- role
"b"- path
[2,0]- changes
[{"node":2,"before":0,"after":0}]- root
0
- The endpoints already belong to the same component.
Equal root sizes retain the first root argument. Decrement component count only for a successful join; sizes at nonroots are stale and have no component-size meaning.
- input
[[1,2],[1,3],[2,3]]- parent
[0,0,0]- size
[3,1,1]- components
1- processed
[{"a":0,"b":1,"merged":true},{"a":0,"b":2,"merged":true},{"a":1,"b":2,"merged":false}]- index
2- edge
[2,3]- answer
[]- phase
"same-set"- current
1- rootA
0- rootB
0- kept
0- attached
null- merged
false
- Remember this most recent cycle-closing occurrence.
The returned pair is a fresh copy in original orientation. On a tree-plus-one-edge input this is the last removable cycle edge; a general multicycle stream has no promised one-edge global repair.
- input
[[1,2],[1,3],[2,3]]- parent
[0,0,0]- size
[3,1,1]- components
1- processed
[{"a":0,"b":1,"merged":true},{"a":0,"b":2,"merged":true},{"a":1,"b":2,"merged":false}]- phase
"candidate"- current
1- index
2- edge
[2,3]- answer
[2,3]
- All candidate connections have been considered.
The count started with the full declared vertex universe, including isolated labels. Duplicate and self edges cannot reduce it.
- input
[[1,2],[1,3],[2,3]]- parent
[0,0,0]- size
[3,1,1]- components
1- processed
[{"a":0,"b":1,"merged":true},{"a":0,"b":2,"merged":true},{"a":1,"b":2,"merged":false}]- phase
"complete"- current
null- answer
[2,3]
- Return the documented count, copied edge, merged rows, or thrown outcome.
DSU links encode membership rather than an original graph path. Walkthrough histories are teaching views, not extra Java workspace.
- result
[2,3]
Two separate cycle-closing occurrences keep the later pair
Input: [[1,2],[2,3],[3,1],[3,4],[4,1]] · Latest copied cycle-closing edge: [4,1]
Step 1 of 20: Initialize one singleton set for every vertex or account.
parent[v]=v and root size is one. Root IDs are implementation representatives, not necessarily the smallest member or an original graph edge.
Phase: initial.
Input undirected occurrences — exact order and orientation
- 0: (1, 2)
- 1: (2, 3)
- 2: (3, 1)
- 3: (3, 4)
- 4: (4, 1)
External labels are positive: label x uses DSU slot x−1. The allocated universe includes every label 1 through the maximum, even unobserved intermediate labels.
Parent forest — arrows are implementation links, not original graph edges
- label 1 (slot 0)parent → 1 (root)root size 1
- label 2 (slot 1)parent → 2 (root)root size 1
- label 3 (slot 2)parent → 3 (root)root size 1
- label 4 (slot 3)parent → 4 (root)root size 1
Component count: 4. Root choices need not be the smallest member.
Current partition — members grouped by representative
- root 1: {1}
- root 2: {2}
- root 3: {3}
- root 4: {4}
Latest copied redundant occurrence — original external labels
Empty.
A failed union certifies an earlier path (or a self-loop). The candidate updates in the separate record step. One-edge global repair is guaranteed only for the simple connected tree-plus-one-edge subset.
Exact arrays and equivalent static steps appear below. Logical partition/map views explain the Java implementation without adding those pictures to its workspace cost.
| Variable | Value |
|---|---|
| input | [[1,2],[2,3],[3,1],[3,4],[4,1]] |
| parent | [0,1,2,3] |
| size | [1,1,1,1] |
| components | 4 |
| processed | [] |
| phase | "initial" |
| current | null |
See the affected Java block
1 import java.util.*; 2 public final class Solution { 3 private static final class Dsu { 4 final int[] parent,size;int components; 5 Dsu(int n){parent=new int[n];size=new int[n];components=n;for(int v=0;v<n;v++){parent[v]=v;size[v]=1;}} 6 int find(int v){while(v!=parent[v]){parent[v]=parent[parent[v]];v=parent[v];}return v;} 7 boolean union(int a,int b){int ra=find(a),rb=find(b);if(ra==rb)return false;if(size[ra]<size[rb]){int swap=ra;ra=rb;rb=swap;}parent[rb]=ra;size[ra]+=size[rb];components--;return true;} 8 } 9 private static int validate(int[][] edges) { 10 Objects.requireNonNull(edges,"edges");int maximum=0;for(int[] edge:edges){if(edge==null||edge.length!=2||edge[0]<1||edge[1]<1||edge[0]>100000||edge[1]>100000)throw new IllegalArgumentException("expected positive labels <=100000");maximum=Math.max(maximum,Math.max(edge[0],edge[1]));}return maximum; 11 } 12 public static int[] redundantEdge(int[][] edges) { 13 int maximum=validate(edges);Dsu dsu=new Dsu(maximum);int[] result=new int[0]; 14 for(int[] edge:edges)if(!dsu.union(edge[0]-1,edge[1]-1))result=new int[]{edge[0],edge[1]}; 15 return result; 16 } 17 public static int[] baseline(int[][] edges) { 18 int maximum=validate(edges);List<List<Integer>> graph=new ArrayList<>();for(int i=0;i<=maximum;i++)graph.add(new ArrayList<>());int[] result=new int[0]; 19 for(int[] edge:edges){boolean[] seen=new boolean[maximum+1];ArrayDeque<Integer> queue=new ArrayDeque<>();seen[edge[0]]=true;queue.addLast(edge[0]);while(!queue.isEmpty()&&!seen[edge[1]]){int v=queue.removeFirst();for(int next:graph.get(v))if(!seen[next]){seen[next]=true;queue.addLast(next);}}if(seen[edge[1]])result=new int[]{edge[0],edge[1]};graph.get(edge[0]).add(edge[1]);graph.get(edge[1]).add(edge[0]);}return result; 20 } 21 } 22
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Initialize one singleton set for every vertex or account.
parent[v]=v and root size is one. Root IDs are implementation representatives, not necessarily the smallest member or an original graph edge.
- input
[[1,2],[2,3],[3,1],[3,4],[4,1]]- parent
[0,1,2,3]- size
[1,1,1,1]- components
4- processed
[]- phase
"initial"- current
null
- Find a representative with iterative path halving.
Each visited nonroot is rewired to its grandparent before jumping there. This can shorten paths without changing the partition; one halving find need not flatten every path completely.
- input
[[1,2],[2,3],[3,1],[3,4],[4,1]]- parent
[0,1,2,3]- size
[1,1,1,1]- components
4- processed
[]- index
0- edge
[1,2]- answer
[]- phase
"find"- current
0- role
"a"- path
[0]- changes
[]- root
0
- Find a representative with iterative path halving.
Each visited nonroot is rewired to its grandparent before jumping there. This can shorten paths without changing the partition; one halving find need not flatten every path completely.
- input
[[1,2],[2,3],[3,1],[3,4],[4,1]]- parent
[0,1,2,3]- size
[1,1,1,1]- components
4- processed
[]- index
0- edge
[1,2]- answer
[]- phase
"find"- current
1- role
"b"- path
[1]- changes
[]- root
1
- Join the smaller root tree under the larger one.
Equal root sizes retain the first root argument. Decrement component count only for a successful join; sizes at nonroots are stale and have no component-size meaning.
- input
[[1,2],[2,3],[3,1],[3,4],[4,1]]- parent
[0,0,2,3]- size
[2,1,1,1]- components
3- processed
[{"a":0,"b":1,"merged":true}]- index
0- edge
[1,2]- answer
[]- phase
"union"- current
0- rootA
0- rootB
1- kept
0- attached
1- merged
true
- Find a representative with iterative path halving.
Each visited nonroot is rewired to its grandparent before jumping there. This can shorten paths without changing the partition; one halving find need not flatten every path completely.
- input
[[1,2],[2,3],[3,1],[3,4],[4,1]]- parent
[0,0,2,3]- size
[2,1,1,1]- components
3- processed
[{"a":0,"b":1,"merged":true}]- index
1- edge
[2,3]- answer
[]- phase
"find"- current
1- role
"a"- path
[1,0]- changes
[{"node":1,"before":0,"after":0}]- root
0
- Find a representative with iterative path halving.
Each visited nonroot is rewired to its grandparent before jumping there. This can shorten paths without changing the partition; one halving find need not flatten every path completely.
- input
[[1,2],[2,3],[3,1],[3,4],[4,1]]- parent
[0,0,2,3]- size
[2,1,1,1]- components
3- processed
[{"a":0,"b":1,"merged":true}]- index
1- edge
[2,3]- answer
[]- phase
"find"- current
2- role
"b"- path
[2]- changes
[]- root
2
- Join the smaller root tree under the larger one.
Equal root sizes retain the first root argument. Decrement component count only for a successful join; sizes at nonroots are stale and have no component-size meaning.
- input
[[1,2],[2,3],[3,1],[3,4],[4,1]]- parent
[0,0,0,3]- size
[3,1,1,1]- components
2- processed
[{"a":0,"b":1,"merged":true},{"a":1,"b":2,"merged":true}]- index
1- edge
[2,3]- answer
[]- phase
"union"- current
1- rootA
0- rootB
2- kept
0- attached
2- merged
true
- Find a representative with iterative path halving.
Each visited nonroot is rewired to its grandparent before jumping there. This can shorten paths without changing the partition; one halving find need not flatten every path completely.
- input
[[1,2],[2,3],[3,1],[3,4],[4,1]]- parent
[0,0,0,3]- size
[3,1,1,1]- components
2- processed
[{"a":0,"b":1,"merged":true},{"a":1,"b":2,"merged":true}]- index
2- edge
[3,1]- answer
[]- phase
"find"- current
2- role
"a"- path
[2,0]- changes
[{"node":2,"before":0,"after":0}]- root
0
- Find a representative with iterative path halving.
Each visited nonroot is rewired to its grandparent before jumping there. This can shorten paths without changing the partition; one halving find need not flatten every path completely.
- input
[[1,2],[2,3],[3,1],[3,4],[4,1]]- parent
[0,0,0,3]- size
[3,1,1,1]- components
2- processed
[{"a":0,"b":1,"merged":true},{"a":1,"b":2,"merged":true}]- index
2- edge
[3,1]- answer
[]- phase
"find"- current
0- role
"b"- path
[0]- changes
[]- root
0
- The endpoints already belong to the same component.
Equal root sizes retain the first root argument. Decrement component count only for a successful join; sizes at nonroots are stale and have no component-size meaning.
- input
[[1,2],[2,3],[3,1],[3,4],[4,1]]- parent
[0,0,0,3]- size
[3,1,1,1]- components
2- processed
[{"a":0,"b":1,"merged":true},{"a":1,"b":2,"merged":true},{"a":2,"b":0,"merged":false}]- index
2- edge
[3,1]- answer
[]- phase
"same-set"- current
2- rootA
0- rootB
0- kept
0- attached
null- merged
false
- Remember this most recent cycle-closing occurrence.
The returned pair is a fresh copy in original orientation. On a tree-plus-one-edge input this is the last removable cycle edge; a general multicycle stream has no promised one-edge global repair.
- input
[[1,2],[2,3],[3,1],[3,4],[4,1]]- parent
[0,0,0,3]- size
[3,1,1,1]- components
2- processed
[{"a":0,"b":1,"merged":true},{"a":1,"b":2,"merged":true},{"a":2,"b":0,"merged":false}]- phase
"candidate"- current
2- index
2- edge
[3,1]- answer
[3,1]
- Find a representative with iterative path halving.
Each visited nonroot is rewired to its grandparent before jumping there. This can shorten paths without changing the partition; one halving find need not flatten every path completely.
- input
[[1,2],[2,3],[3,1],[3,4],[4,1]]- parent
[0,0,0,3]- size
[3,1,1,1]- components
2- processed
[{"a":0,"b":1,"merged":true},{"a":1,"b":2,"merged":true},{"a":2,"b":0,"merged":false}]- index
3- edge
[3,4]- answer
[3,1]- phase
"find"- current
2- role
"a"- path
[2,0]- changes
[{"node":2,"before":0,"after":0}]- root
0
- Find a representative with iterative path halving.
Each visited nonroot is rewired to its grandparent before jumping there. This can shorten paths without changing the partition; one halving find need not flatten every path completely.
- input
[[1,2],[2,3],[3,1],[3,4],[4,1]]- parent
[0,0,0,3]- size
[3,1,1,1]- components
2- processed
[{"a":0,"b":1,"merged":true},{"a":1,"b":2,"merged":true},{"a":2,"b":0,"merged":false}]- index
3- edge
[3,4]- answer
[3,1]- phase
"find"- current
3- role
"b"- path
[3]- changes
[]- root
3
- Join the smaller root tree under the larger one.
Equal root sizes retain the first root argument. Decrement component count only for a successful join; sizes at nonroots are stale and have no component-size meaning.
- input
[[1,2],[2,3],[3,1],[3,4],[4,1]]- parent
[0,0,0,0]- size
[4,1,1,1]- components
1- processed
[{"a":0,"b":1,"merged":true},{"a":1,"b":2,"merged":true},{"a":2,"b":0,"merged":false},{"a":2,"b":3,"merged":true}]- index
3- edge
[3,4]- answer
[3,1]- phase
"union"- current
2- rootA
0- rootB
3- kept
0- attached
3- merged
true
- Find a representative with iterative path halving.
Each visited nonroot is rewired to its grandparent before jumping there. This can shorten paths without changing the partition; one halving find need not flatten every path completely.
- input
[[1,2],[2,3],[3,1],[3,4],[4,1]]- parent
[0,0,0,0]- size
[4,1,1,1]- components
1- processed
[{"a":0,"b":1,"merged":true},{"a":1,"b":2,"merged":true},{"a":2,"b":0,"merged":false},{"a":2,"b":3,"merged":true}]- index
4- edge
[4,1]- answer
[3,1]- phase
"find"- current
3- role
"a"- path
[3,0]- changes
[{"node":3,"before":0,"after":0}]- root
0
- Find a representative with iterative path halving.
Each visited nonroot is rewired to its grandparent before jumping there. This can shorten paths without changing the partition; one halving find need not flatten every path completely.
- input
[[1,2],[2,3],[3,1],[3,4],[4,1]]- parent
[0,0,0,0]- size
[4,1,1,1]- components
1- processed
[{"a":0,"b":1,"merged":true},{"a":1,"b":2,"merged":true},{"a":2,"b":0,"merged":false},{"a":2,"b":3,"merged":true}]- index
4- edge
[4,1]- answer
[3,1]- phase
"find"- current
0- role
"b"- path
[0]- changes
[]- root
0
- The endpoints already belong to the same component.
Equal root sizes retain the first root argument. Decrement component count only for a successful join; sizes at nonroots are stale and have no component-size meaning.
- input
[[1,2],[2,3],[3,1],[3,4],[4,1]]- parent
[0,0,0,0]- size
[4,1,1,1]- components
1- processed
[{"a":0,"b":1,"merged":true},{"a":1,"b":2,"merged":true},{"a":2,"b":0,"merged":false},{"a":2,"b":3,"merged":true},{"a":3,"b":0,"merged":false}]- index
4- edge
[4,1]- answer
[3,1]- phase
"same-set"- current
3- rootA
0- rootB
0- kept
0- attached
null- merged
false
- Remember this most recent cycle-closing occurrence.
The returned pair is a fresh copy in original orientation. On a tree-plus-one-edge input this is the last removable cycle edge; a general multicycle stream has no promised one-edge global repair.
- input
[[1,2],[2,3],[3,1],[3,4],[4,1]]- parent
[0,0,0,0]- size
[4,1,1,1]- components
1- processed
[{"a":0,"b":1,"merged":true},{"a":1,"b":2,"merged":true},{"a":2,"b":0,"merged":false},{"a":2,"b":3,"merged":true},{"a":3,"b":0,"merged":false}]- phase
"candidate"- current
3- index
4- edge
[4,1]- answer
[4,1]
- All candidate connections have been considered.
The count started with the full declared vertex universe, including isolated labels. Duplicate and self edges cannot reduce it.
- input
[[1,2],[2,3],[3,1],[3,4],[4,1]]- parent
[0,0,0,0]- size
[4,1,1,1]- components
1- processed
[{"a":0,"b":1,"merged":true},{"a":1,"b":2,"merged":true},{"a":2,"b":0,"merged":false},{"a":2,"b":3,"merged":true},{"a":3,"b":0,"merged":false}]- phase
"complete"- current
null- answer
[4,1]
- Return the documented count, copied edge, merged rows, or thrown outcome.
DSU links encode membership rather than an original graph path. Walkthrough histories are teaching views, not extra Java workspace.
- result
[4,1]
Path halving during an unsuccessful balanced-tree union
Input: [[1,2],[3,4],[1,3],[2,4]] · Latest copied cycle-closing edge: [2,4]
Step 1 of 16: Initialize one singleton set for every vertex or account.
parent[v]=v and root size is one. Root IDs are implementation representatives, not necessarily the smallest member or an original graph edge.
Phase: initial.
Input undirected occurrences — exact order and orientation
- 0: (1, 2)
- 1: (3, 4)
- 2: (1, 3)
- 3: (2, 4)
External labels are positive: label x uses DSU slot x−1. The allocated universe includes every label 1 through the maximum, even unobserved intermediate labels.
Parent forest — arrows are implementation links, not original graph edges
- label 1 (slot 0)parent → 1 (root)root size 1
- label 2 (slot 1)parent → 2 (root)root size 1
- label 3 (slot 2)parent → 3 (root)root size 1
- label 4 (slot 3)parent → 4 (root)root size 1
Component count: 4. Root choices need not be the smallest member.
Current partition — members grouped by representative
- root 1: {1}
- root 2: {2}
- root 3: {3}
- root 4: {4}
Latest copied redundant occurrence — original external labels
Empty.
A failed union certifies an earlier path (or a self-loop). The candidate updates in the separate record step. One-edge global repair is guaranteed only for the simple connected tree-plus-one-edge subset.
Exact arrays and equivalent static steps appear below. Logical partition/map views explain the Java implementation without adding those pictures to its workspace cost.
| Variable | Value |
|---|---|
| input | [[1,2],[3,4],[1,3],[2,4]] |
| parent | [0,1,2,3] |
| size | [1,1,1,1] |
| components | 4 |
| processed | [] |
| phase | "initial" |
| current | null |
See the affected Java block
1 import java.util.*; 2 public final class Solution { 3 private static final class Dsu { 4 final int[] parent,size;int components; 5 Dsu(int n){parent=new int[n];size=new int[n];components=n;for(int v=0;v<n;v++){parent[v]=v;size[v]=1;}} 6 int find(int v){while(v!=parent[v]){parent[v]=parent[parent[v]];v=parent[v];}return v;} 7 boolean union(int a,int b){int ra=find(a),rb=find(b);if(ra==rb)return false;if(size[ra]<size[rb]){int swap=ra;ra=rb;rb=swap;}parent[rb]=ra;size[ra]+=size[rb];components--;return true;} 8 } 9 private static int validate(int[][] edges) { 10 Objects.requireNonNull(edges,"edges");int maximum=0;for(int[] edge:edges){if(edge==null||edge.length!=2||edge[0]<1||edge[1]<1||edge[0]>100000||edge[1]>100000)throw new IllegalArgumentException("expected positive labels <=100000");maximum=Math.max(maximum,Math.max(edge[0],edge[1]));}return maximum; 11 } 12 public static int[] redundantEdge(int[][] edges) { 13 int maximum=validate(edges);Dsu dsu=new Dsu(maximum);int[] result=new int[0]; 14 for(int[] edge:edges)if(!dsu.union(edge[0]-1,edge[1]-1))result=new int[]{edge[0],edge[1]}; 15 return result; 16 } 17 public static int[] baseline(int[][] edges) { 18 int maximum=validate(edges);List<List<Integer>> graph=new ArrayList<>();for(int i=0;i<=maximum;i++)graph.add(new ArrayList<>());int[] result=new int[0]; 19 for(int[] edge:edges){boolean[] seen=new boolean[maximum+1];ArrayDeque<Integer> queue=new ArrayDeque<>();seen[edge[0]]=true;queue.addLast(edge[0]);while(!queue.isEmpty()&&!seen[edge[1]]){int v=queue.removeFirst();for(int next:graph.get(v))if(!seen[next]){seen[next]=true;queue.addLast(next);}}if(seen[edge[1]])result=new int[]{edge[0],edge[1]};graph.get(edge[0]).add(edge[1]);graph.get(edge[1]).add(edge[0]);}return result; 20 } 21 } 22
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Initialize one singleton set for every vertex or account.
parent[v]=v and root size is one. Root IDs are implementation representatives, not necessarily the smallest member or an original graph edge.
- input
[[1,2],[3,4],[1,3],[2,4]]- parent
[0,1,2,3]- size
[1,1,1,1]- components
4- processed
[]- phase
"initial"- current
null
- Find a representative with iterative path halving.
Each visited nonroot is rewired to its grandparent before jumping there. This can shorten paths without changing the partition; one halving find need not flatten every path completely.
- input
[[1,2],[3,4],[1,3],[2,4]]- parent
[0,1,2,3]- size
[1,1,1,1]- components
4- processed
[]- index
0- edge
[1,2]- answer
[]- phase
"find"- current
0- role
"a"- path
[0]- changes
[]- root
0
- Find a representative with iterative path halving.
Each visited nonroot is rewired to its grandparent before jumping there. This can shorten paths without changing the partition; one halving find need not flatten every path completely.
- input
[[1,2],[3,4],[1,3],[2,4]]- parent
[0,1,2,3]- size
[1,1,1,1]- components
4- processed
[]- index
0- edge
[1,2]- answer
[]- phase
"find"- current
1- role
"b"- path
[1]- changes
[]- root
1
- Join the smaller root tree under the larger one.
Equal root sizes retain the first root argument. Decrement component count only for a successful join; sizes at nonroots are stale and have no component-size meaning.
- input
[[1,2],[3,4],[1,3],[2,4]]- parent
[0,0,2,3]- size
[2,1,1,1]- components
3- processed
[{"a":0,"b":1,"merged":true}]- index
0- edge
[1,2]- answer
[]- phase
"union"- current
0- rootA
0- rootB
1- kept
0- attached
1- merged
true
- Find a representative with iterative path halving.
Each visited nonroot is rewired to its grandparent before jumping there. This can shorten paths without changing the partition; one halving find need not flatten every path completely.
- input
[[1,2],[3,4],[1,3],[2,4]]- parent
[0,0,2,3]- size
[2,1,1,1]- components
3- processed
[{"a":0,"b":1,"merged":true}]- index
1- edge
[3,4]- answer
[]- phase
"find"- current
2- role
"a"- path
[2]- changes
[]- root
2
- Find a representative with iterative path halving.
Each visited nonroot is rewired to its grandparent before jumping there. This can shorten paths without changing the partition; one halving find need not flatten every path completely.
- input
[[1,2],[3,4],[1,3],[2,4]]- parent
[0,0,2,3]- size
[2,1,1,1]- components
3- processed
[{"a":0,"b":1,"merged":true}]- index
1- edge
[3,4]- answer
[]- phase
"find"- current
3- role
"b"- path
[3]- changes
[]- root
3
- Join the smaller root tree under the larger one.
Equal root sizes retain the first root argument. Decrement component count only for a successful join; sizes at nonroots are stale and have no component-size meaning.
- input
[[1,2],[3,4],[1,3],[2,4]]- parent
[0,0,2,2]- size
[2,1,2,1]- components
2- processed
[{"a":0,"b":1,"merged":true},{"a":2,"b":3,"merged":true}]- index
1- edge
[3,4]- answer
[]- phase
"union"- current
2- rootA
2- rootB
3- kept
2- attached
3- merged
true
- Find a representative with iterative path halving.
Each visited nonroot is rewired to its grandparent before jumping there. This can shorten paths without changing the partition; one halving find need not flatten every path completely.
- input
[[1,2],[3,4],[1,3],[2,4]]- parent
[0,0,2,2]- size
[2,1,2,1]- components
2- processed
[{"a":0,"b":1,"merged":true},{"a":2,"b":3,"merged":true}]- index
2- edge
[1,3]- answer
[]- phase
"find"- current
0- role
"a"- path
[0]- changes
[]- root
0
- Find a representative with iterative path halving.
Each visited nonroot is rewired to its grandparent before jumping there. This can shorten paths without changing the partition; one halving find need not flatten every path completely.
- input
[[1,2],[3,4],[1,3],[2,4]]- parent
[0,0,2,2]- size
[2,1,2,1]- components
2- processed
[{"a":0,"b":1,"merged":true},{"a":2,"b":3,"merged":true}]- index
2- edge
[1,3]- answer
[]- phase
"find"- current
2- role
"b"- path
[2]- changes
[]- root
2
- Join the smaller root tree under the larger one.
Equal root sizes retain the first root argument. Decrement component count only for a successful join; sizes at nonroots are stale and have no component-size meaning.
- input
[[1,2],[3,4],[1,3],[2,4]]- parent
[0,0,0,2]- size
[4,1,2,1]- components
1- processed
[{"a":0,"b":1,"merged":true},{"a":2,"b":3,"merged":true},{"a":0,"b":2,"merged":true}]- index
2- edge
[1,3]- answer
[]- phase
"union"- current
0- rootA
0- rootB
2- kept
0- attached
2- merged
true
- Find a representative with iterative path halving.
Each visited nonroot is rewired to its grandparent before jumping there. This can shorten paths without changing the partition; one halving find need not flatten every path completely.
- input
[[1,2],[3,4],[1,3],[2,4]]- parent
[0,0,0,2]- size
[4,1,2,1]- components
1- processed
[{"a":0,"b":1,"merged":true},{"a":2,"b":3,"merged":true},{"a":0,"b":2,"merged":true}]- index
3- edge
[2,4]- answer
[]- phase
"find"- current
1- role
"a"- path
[1,0]- changes
[{"node":1,"before":0,"after":0}]- root
0
- Find a representative with iterative path halving.
Each visited nonroot is rewired to its grandparent before jumping there. This can shorten paths without changing the partition; one halving find need not flatten every path completely.
- input
[[1,2],[3,4],[1,3],[2,4]]- parent
[0,0,0,0]- size
[4,1,2,1]- components
1- processed
[{"a":0,"b":1,"merged":true},{"a":2,"b":3,"merged":true},{"a":0,"b":2,"merged":true}]- index
3- edge
[2,4]- answer
[]- phase
"find"- current
3- role
"b"- path
[3,0]- changes
[{"node":3,"before":2,"after":0}]- root
0
- The endpoints already belong to the same component.
Equal root sizes retain the first root argument. Decrement component count only for a successful join; sizes at nonroots are stale and have no component-size meaning.
- input
[[1,2],[3,4],[1,3],[2,4]]- parent
[0,0,0,0]- size
[4,1,2,1]- components
1- processed
[{"a":0,"b":1,"merged":true},{"a":2,"b":3,"merged":true},{"a":0,"b":2,"merged":true},{"a":1,"b":3,"merged":false}]- index
3- edge
[2,4]- answer
[]- phase
"same-set"- current
1- rootA
0- rootB
0- kept
0- attached
null- merged
false
- Remember this most recent cycle-closing occurrence.
The returned pair is a fresh copy in original orientation. On a tree-plus-one-edge input this is the last removable cycle edge; a general multicycle stream has no promised one-edge global repair.
- input
[[1,2],[3,4],[1,3],[2,4]]- parent
[0,0,0,0]- size
[4,1,2,1]- components
1- processed
[{"a":0,"b":1,"merged":true},{"a":2,"b":3,"merged":true},{"a":0,"b":2,"merged":true},{"a":1,"b":3,"merged":false}]- phase
"candidate"- current
1- index
3- edge
[2,4]- answer
[2,4]
- All candidate connections have been considered.
The count started with the full declared vertex universe, including isolated labels. Duplicate and self edges cannot reduce it.
- input
[[1,2],[3,4],[1,3],[2,4]]- parent
[0,0,0,0]- size
[4,1,2,1]- components
1- processed
[{"a":0,"b":1,"merged":true},{"a":2,"b":3,"merged":true},{"a":0,"b":2,"merged":true},{"a":1,"b":3,"merged":false}]- phase
"complete"- current
null- answer
[2,4]
- Return the documented count, copied edge, merged rows, or thrown outcome.
DSU links encode membership rather than an original graph path. Walkthrough histories are teaching views, not extra Java workspace.
- result
[2,4]
A self-loop closes a cycle immediately
Input: [[2,2]] · Latest copied cycle-closing edge: [2,2]
Step 1 of 7: Initialize one singleton set for every vertex or account.
parent[v]=v and root size is one. Root IDs are implementation representatives, not necessarily the smallest member or an original graph edge.
Phase: initial.
Input undirected occurrences — exact order and orientation
- 0: (2, 2)
External labels are positive: label x uses DSU slot x−1. The allocated universe includes every label 1 through the maximum, even unobserved intermediate labels.
Parent forest — arrows are implementation links, not original graph edges
- label 1 (slot 0)parent → 1 (root)root size 1
- label 2 (slot 1)parent → 2 (root)root size 1
Component count: 2. Root choices need not be the smallest member.
Current partition — members grouped by representative
- root 1: {1}
- root 2: {2}
Latest copied redundant occurrence — original external labels
Empty.
A failed union certifies an earlier path (or a self-loop). The candidate updates in the separate record step. One-edge global repair is guaranteed only for the simple connected tree-plus-one-edge subset.
Exact arrays and equivalent static steps appear below. Logical partition/map views explain the Java implementation without adding those pictures to its workspace cost.
| Variable | Value |
|---|---|
| input | [[2,2]] |
| parent | [0,1] |
| size | [1,1] |
| components | 2 |
| processed | [] |
| phase | "initial" |
| current | null |
See the affected Java block
1 import java.util.*; 2 public final class Solution { 3 private static final class Dsu { 4 final int[] parent,size;int components; 5 Dsu(int n){parent=new int[n];size=new int[n];components=n;for(int v=0;v<n;v++){parent[v]=v;size[v]=1;}} 6 int find(int v){while(v!=parent[v]){parent[v]=parent[parent[v]];v=parent[v];}return v;} 7 boolean union(int a,int b){int ra=find(a),rb=find(b);if(ra==rb)return false;if(size[ra]<size[rb]){int swap=ra;ra=rb;rb=swap;}parent[rb]=ra;size[ra]+=size[rb];components--;return true;} 8 } 9 private static int validate(int[][] edges) { 10 Objects.requireNonNull(edges,"edges");int maximum=0;for(int[] edge:edges){if(edge==null||edge.length!=2||edge[0]<1||edge[1]<1||edge[0]>100000||edge[1]>100000)throw new IllegalArgumentException("expected positive labels <=100000");maximum=Math.max(maximum,Math.max(edge[0],edge[1]));}return maximum; 11 } 12 public static int[] redundantEdge(int[][] edges) { 13 int maximum=validate(edges);Dsu dsu=new Dsu(maximum);int[] result=new int[0]; 14 for(int[] edge:edges)if(!dsu.union(edge[0]-1,edge[1]-1))result=new int[]{edge[0],edge[1]}; 15 return result; 16 } 17 public static int[] baseline(int[][] edges) { 18 int maximum=validate(edges);List<List<Integer>> graph=new ArrayList<>();for(int i=0;i<=maximum;i++)graph.add(new ArrayList<>());int[] result=new int[0]; 19 for(int[] edge:edges){boolean[] seen=new boolean[maximum+1];ArrayDeque<Integer> queue=new ArrayDeque<>();seen[edge[0]]=true;queue.addLast(edge[0]);while(!queue.isEmpty()&&!seen[edge[1]]){int v=queue.removeFirst();for(int next:graph.get(v))if(!seen[next]){seen[next]=true;queue.addLast(next);}}if(seen[edge[1]])result=new int[]{edge[0],edge[1]};graph.get(edge[0]).add(edge[1]);graph.get(edge[1]).add(edge[0]);}return result; 20 } 21 } 22
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Initialize one singleton set for every vertex or account.
parent[v]=v and root size is one. Root IDs are implementation representatives, not necessarily the smallest member or an original graph edge.
- input
[[2,2]]- parent
[0,1]- size
[1,1]- components
2- processed
[]- phase
"initial"- current
null
- Find a representative with iterative path halving.
Each visited nonroot is rewired to its grandparent before jumping there. This can shorten paths without changing the partition; one halving find need not flatten every path completely.
- input
[[2,2]]- parent
[0,1]- size
[1,1]- components
2- processed
[]- index
0- edge
[2,2]- answer
[]- phase
"find"- current
1- role
"a"- path
[1]- changes
[]- root
1
- Find a representative with iterative path halving.
Each visited nonroot is rewired to its grandparent before jumping there. This can shorten paths without changing the partition; one halving find need not flatten every path completely.
- input
[[2,2]]- parent
[0,1]- size
[1,1]- components
2- processed
[]- index
0- edge
[2,2]- answer
[]- phase
"find"- current
1- role
"b"- path
[1]- changes
[]- root
1
- The endpoints already belong to the same component.
Equal root sizes retain the first root argument. Decrement component count only for a successful join; sizes at nonroots are stale and have no component-size meaning.
- input
[[2,2]]- parent
[0,1]- size
[1,1]- components
2- processed
[{"a":1,"b":1,"merged":false}]- index
0- edge
[2,2]- answer
[]- phase
"same-set"- current
1- rootA
1- rootB
1- kept
1- attached
null- merged
false
- Remember this most recent cycle-closing occurrence.
The returned pair is a fresh copy in original orientation. On a tree-plus-one-edge input this is the last removable cycle edge; a general multicycle stream has no promised one-edge global repair.
- input
[[2,2]]- parent
[0,1]- size
[1,1]- components
2- processed
[{"a":1,"b":1,"merged":false}]- phase
"candidate"- current
1- index
0- edge
[2,2]- answer
[2,2]
- All candidate connections have been considered.
The count started with the full declared vertex universe, including isolated labels. Duplicate and self edges cannot reduce it.
- input
[[2,2]]- parent
[0,1]- size
[1,1]- components
2- processed
[{"a":1,"b":1,"merged":false}]- phase
"complete"- current
null- answer
[2,2]
- Return the documented count, copied edge, merged rows, or thrown outcome.
DSU links encode membership rather than an original graph path. Walkthrough histories are teaching views, not extra Java workspace.
- result
[2,2]
An acyclic forest has no redundant occurrence
Input: [[1,2],[3,4]] · Latest copied cycle-closing edge: []
Step 1 of 9: Initialize one singleton set for every vertex or account.
parent[v]=v and root size is one. Root IDs are implementation representatives, not necessarily the smallest member or an original graph edge.
Phase: initial.
Input undirected occurrences — exact order and orientation
- 0: (1, 2)
- 1: (3, 4)
External labels are positive: label x uses DSU slot x−1. The allocated universe includes every label 1 through the maximum, even unobserved intermediate labels.
Parent forest — arrows are implementation links, not original graph edges
- label 1 (slot 0)parent → 1 (root)root size 1
- label 2 (slot 1)parent → 2 (root)root size 1
- label 3 (slot 2)parent → 3 (root)root size 1
- label 4 (slot 3)parent → 4 (root)root size 1
Component count: 4. Root choices need not be the smallest member.
Current partition — members grouped by representative
- root 1: {1}
- root 2: {2}
- root 3: {3}
- root 4: {4}
Latest copied redundant occurrence — original external labels
Empty.
A failed union certifies an earlier path (or a self-loop). The candidate updates in the separate record step. One-edge global repair is guaranteed only for the simple connected tree-plus-one-edge subset.
Exact arrays and equivalent static steps appear below. Logical partition/map views explain the Java implementation without adding those pictures to its workspace cost.
| Variable | Value |
|---|---|
| input | [[1,2],[3,4]] |
| parent | [0,1,2,3] |
| size | [1,1,1,1] |
| components | 4 |
| processed | [] |
| phase | "initial" |
| current | null |
See the affected Java block
1 import java.util.*; 2 public final class Solution { 3 private static final class Dsu { 4 final int[] parent,size;int components; 5 Dsu(int n){parent=new int[n];size=new int[n];components=n;for(int v=0;v<n;v++){parent[v]=v;size[v]=1;}} 6 int find(int v){while(v!=parent[v]){parent[v]=parent[parent[v]];v=parent[v];}return v;} 7 boolean union(int a,int b){int ra=find(a),rb=find(b);if(ra==rb)return false;if(size[ra]<size[rb]){int swap=ra;ra=rb;rb=swap;}parent[rb]=ra;size[ra]+=size[rb];components--;return true;} 8 } 9 private static int validate(int[][] edges) { 10 Objects.requireNonNull(edges,"edges");int maximum=0;for(int[] edge:edges){if(edge==null||edge.length!=2||edge[0]<1||edge[1]<1||edge[0]>100000||edge[1]>100000)throw new IllegalArgumentException("expected positive labels <=100000");maximum=Math.max(maximum,Math.max(edge[0],edge[1]));}return maximum; 11 } 12 public static int[] redundantEdge(int[][] edges) { 13 int maximum=validate(edges);Dsu dsu=new Dsu(maximum);int[] result=new int[0]; 14 for(int[] edge:edges)if(!dsu.union(edge[0]-1,edge[1]-1))result=new int[]{edge[0],edge[1]}; 15 return result; 16 } 17 public static int[] baseline(int[][] edges) { 18 int maximum=validate(edges);List<List<Integer>> graph=new ArrayList<>();for(int i=0;i<=maximum;i++)graph.add(new ArrayList<>());int[] result=new int[0]; 19 for(int[] edge:edges){boolean[] seen=new boolean[maximum+1];ArrayDeque<Integer> queue=new ArrayDeque<>();seen[edge[0]]=true;queue.addLast(edge[0]);while(!queue.isEmpty()&&!seen[edge[1]]){int v=queue.removeFirst();for(int next:graph.get(v))if(!seen[next]){seen[next]=true;queue.addLast(next);}}if(seen[edge[1]])result=new int[]{edge[0],edge[1]};graph.get(edge[0]).add(edge[1]);graph.get(edge[1]).add(edge[0]);}return result; 20 } 21 } 22
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Initialize one singleton set for every vertex or account.
parent[v]=v and root size is one. Root IDs are implementation representatives, not necessarily the smallest member or an original graph edge.
- input
[[1,2],[3,4]]- parent
[0,1,2,3]- size
[1,1,1,1]- components
4- processed
[]- phase
"initial"- current
null
- Find a representative with iterative path halving.
Each visited nonroot is rewired to its grandparent before jumping there. This can shorten paths without changing the partition; one halving find need not flatten every path completely.
- input
[[1,2],[3,4]]- parent
[0,1,2,3]- size
[1,1,1,1]- components
4- processed
[]- index
0- edge
[1,2]- answer
[]- phase
"find"- current
0- role
"a"- path
[0]- changes
[]- root
0
- Find a representative with iterative path halving.
Each visited nonroot is rewired to its grandparent before jumping there. This can shorten paths without changing the partition; one halving find need not flatten every path completely.
- input
[[1,2],[3,4]]- parent
[0,1,2,3]- size
[1,1,1,1]- components
4- processed
[]- index
0- edge
[1,2]- answer
[]- phase
"find"- current
1- role
"b"- path
[1]- changes
[]- root
1
- Join the smaller root tree under the larger one.
Equal root sizes retain the first root argument. Decrement component count only for a successful join; sizes at nonroots are stale and have no component-size meaning.
- input
[[1,2],[3,4]]- parent
[0,0,2,3]- size
[2,1,1,1]- components
3- processed
[{"a":0,"b":1,"merged":true}]- index
0- edge
[1,2]- answer
[]- phase
"union"- current
0- rootA
0- rootB
1- kept
0- attached
1- merged
true
- Find a representative with iterative path halving.
Each visited nonroot is rewired to its grandparent before jumping there. This can shorten paths without changing the partition; one halving find need not flatten every path completely.
- input
[[1,2],[3,4]]- parent
[0,0,2,3]- size
[2,1,1,1]- components
3- processed
[{"a":0,"b":1,"merged":true}]- index
1- edge
[3,4]- answer
[]- phase
"find"- current
2- role
"a"- path
[2]- changes
[]- root
2
- Find a representative with iterative path halving.
Each visited nonroot is rewired to its grandparent before jumping there. This can shorten paths without changing the partition; one halving find need not flatten every path completely.
- input
[[1,2],[3,4]]- parent
[0,0,2,3]- size
[2,1,1,1]- components
3- processed
[{"a":0,"b":1,"merged":true}]- index
1- edge
[3,4]- answer
[]- phase
"find"- current
3- role
"b"- path
[3]- changes
[]- root
3
- Join the smaller root tree under the larger one.
Equal root sizes retain the first root argument. Decrement component count only for a successful join; sizes at nonroots are stale and have no component-size meaning.
- input
[[1,2],[3,4]]- parent
[0,0,2,2]- size
[2,1,2,1]- components
2- processed
[{"a":0,"b":1,"merged":true},{"a":2,"b":3,"merged":true}]- index
1- edge
[3,4]- answer
[]- phase
"union"- current
2- rootA
2- rootB
3- kept
2- attached
3- merged
true
- All candidate connections have been considered.
The count started with the full declared vertex universe, including isolated labels. Duplicate and self edges cannot reduce it.
- input
[[1,2],[3,4]]- parent
[0,0,2,2]- size
[2,1,2,1]- components
2- processed
[{"a":0,"b":1,"merged":true},{"a":2,"b":3,"merged":true}]- phase
"complete"- current
null- answer
[]
- Return the documented count, copied edge, merged rows, or thrown outcome.
DSU links encode membership rather than an original graph path. Walkthrough histories are teaching views, not extra Java workspace.
- result
[]
Empty edge stream
Input: [] · Latest copied cycle-closing edge: []
Step 1 of 3: Initialize one singleton set for every vertex or account.
parent[v]=v and root size is one. Root IDs are implementation representatives, not necessarily the smallest member or an original graph edge.
Phase: initial.
Input undirected occurrences — exact order and orientation
Empty.
External labels are positive: label x uses DSU slot x−1. The allocated universe includes every label 1 through the maximum, even unobserved intermediate labels.
Parent forest — arrows are implementation links, not original graph edges
No vertices.
Component count: 0. Root choices need not be the smallest member.
Current partition — members grouped by representative
Empty.
Latest copied redundant occurrence — original external labels
Empty.
A failed union certifies an earlier path (or a self-loop). The candidate updates in the separate record step. One-edge global repair is guaranteed only for the simple connected tree-plus-one-edge subset.
Exact arrays and equivalent static steps appear below. Logical partition/map views explain the Java implementation without adding those pictures to its workspace cost.
| Variable | Value |
|---|---|
| input | [] |
| parent | [] |
| size | [] |
| components | 0 |
| processed | [] |
| phase | "initial" |
| current | null |
See the affected Java block
1 import java.util.*; 2 public final class Solution { 3 private static final class Dsu { 4 final int[] parent,size;int components; 5 Dsu(int n){parent=new int[n];size=new int[n];components=n;for(int v=0;v<n;v++){parent[v]=v;size[v]=1;}} 6 int find(int v){while(v!=parent[v]){parent[v]=parent[parent[v]];v=parent[v];}return v;} 7 boolean union(int a,int b){int ra=find(a),rb=find(b);if(ra==rb)return false;if(size[ra]<size[rb]){int swap=ra;ra=rb;rb=swap;}parent[rb]=ra;size[ra]+=size[rb];components--;return true;} 8 } 9 private static int validate(int[][] edges) { 10 Objects.requireNonNull(edges,"edges");int maximum=0;for(int[] edge:edges){if(edge==null||edge.length!=2||edge[0]<1||edge[1]<1||edge[0]>100000||edge[1]>100000)throw new IllegalArgumentException("expected positive labels <=100000");maximum=Math.max(maximum,Math.max(edge[0],edge[1]));}return maximum; 11 } 12 public static int[] redundantEdge(int[][] edges) { 13 int maximum=validate(edges);Dsu dsu=new Dsu(maximum);int[] result=new int[0]; 14 for(int[] edge:edges)if(!dsu.union(edge[0]-1,edge[1]-1))result=new int[]{edge[0],edge[1]}; 15 return result; 16 } 17 public static int[] baseline(int[][] edges) { 18 int maximum=validate(edges);List<List<Integer>> graph=new ArrayList<>();for(int i=0;i<=maximum;i++)graph.add(new ArrayList<>());int[] result=new int[0]; 19 for(int[] edge:edges){boolean[] seen=new boolean[maximum+1];ArrayDeque<Integer> queue=new ArrayDeque<>();seen[edge[0]]=true;queue.addLast(edge[0]);while(!queue.isEmpty()&&!seen[edge[1]]){int v=queue.removeFirst();for(int next:graph.get(v))if(!seen[next]){seen[next]=true;queue.addLast(next);}}if(seen[edge[1]])result=new int[]{edge[0],edge[1]};graph.get(edge[0]).add(edge[1]);graph.get(edge[1]).add(edge[0]);}return result; 20 } 21 } 22
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Initialize one singleton set for every vertex or account.
parent[v]=v and root size is one. Root IDs are implementation representatives, not necessarily the smallest member or an original graph edge.
- input
[]- parent
[]- size
[]- components
0- processed
[]- phase
"initial"- current
null
- All candidate connections have been considered.
The count started with the full declared vertex universe, including isolated labels. Duplicate and self edges cannot reduce it.
- input
[]- parent
[]- size
[]- components
0- processed
[]- phase
"complete"- current
null- answer
[]
- Return the documented count, copied edge, merged rows, or thrown outcome.
DSU links encode membership rather than an original graph path. Walkthrough histories are teaching views, not extra Java workspace.
- result
[]
Test the contract
Input:
No edges or an acyclic forest
Output:fresh []No cycle-closing occurrence.
Input:
Self-loop and reversed duplicate
Output:latest qualifying original pairThe contract includes multigraph occurrences.
Input:
Connected tree plus one extra simple edge
Output:last deletable cycle edgeIndependent removal/reachability oracle checks the canonical subset.
Input:
Sparse labels near 100000
Output:correct copied pair with O(U) storageIndex translation and universe cost.
Input:
100,000-label chain plus closing edge
Output:the final copied edgeNo recursive stack dependence.
Common mistakes and counterexamples
Stop at the first failed union
Counterexample: A later cycle-closing occurrence exists in the five-edge example.
Keep the latest copied candidate.
Return an input row directly
Counterexample: Editing the returned pair would modify caller-owned edges.
Allocate a two-int result copy.
Assume one deletion repairs every accepted input
Counterexample: A multicycle stream can remain cyclic after deleting the returned occurrence.
State the general prefix rule separately from the unicyclic repair subset.
Confuse positive labels with DSU array indices
Counterexample: Label 100000 is legal but array index 100000 is outside a U-length array.
Translate both endpoints by subtracting one.
Follow-ups
Return the actual cycle path.
Retain original accepted edges as a spanning forest and find the earlier path between the failed edge endpoints. DSU parent pointers do not generally correspond to original edges.
Handle directed redundant connections.
Indegree constraints and directed cycles require a different proof; undirected DSU failure alone does not characterize the directed repair problem.
Support very large sparse labels.
Coordinate-compress observed labels, keeping the original labels for output. Count map/key costs and distinguish observed vertices from a declared dense universe.
Your Java attempt
Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.
Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.
No unsaved text changes · 170/20,000 characters
Self-review
Use the checklist to test your explanation. Checks apply to this visit.