DSA-112 · FOCUSED PRACTICE
Connected Components in an Undirected Graph
Core · Java 21 · Version 1 · editorial draft
Java reference and baseline verified on JDK 21: 71759 deterministic checks. Learner drafts are not executed.
Understand the problem
Return the number of connected components in an undirected graph with an explicit vertex count, including isolated vertices.
- n is nonnegative and vertices are labeled 0..n-1. At most 100,000 vertices and 200,000 edge occurrences are size preconditions. Negative n throws IllegalArgumentException. Null outer edge array throws NullPointerException; null/non-pair rows and out-of-range endpoints throw IllegalArgumentException before processing. n=0 is valid only with no valid endpoint rows.
- Every pair is an undirected occurrence. Duplicate/reversed pairs, self-loops, disconnected graphs, and an empty edge set are allowed. An isolated vertex is a component even if its label never appears in any pair. Shared input row objects are allowed because inputs are read-only.
- Preserve every input value and row identity. Return a single int between zero and n, using private DSU state. The represented partition depends on connectivity, not edge order, tie-breaking, root labels, or how much find compression has occurred.
Examples
Input:
n=5, edges=[[0,1],[1,2],[3,4]]
Output:2The components are {0,1,2} and {3,4}.
Input:
n=4, edges=[[0,1],[1,0],[2,2]]
Output:3Only the first occurrence joins two sets; 2 and the absent-from-edges vertex 3 are isolated components.
Input:
n=0, edges=[]
Output:0The empty universe has no components.
Input:
n=4, edges=[]
Output:4The vertex count, not observed endpoints, defines the universe.
Before you start
- Undirected component partitions including isolated vertices
- Union by size, path halving, and successful-merge accounting
Recognize the structure
This input is a sparse edge stream with an explicit vertex universe. DSU can consume it without storing both directions of every edge, while preserving a component-count invariant. For a single static graph, BFS/DFS remains a linear-time alternative; DSU is particularly natural for repeated insertions and connectivity queries.
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 · 163/20,000 characters
Self-review
Use the checklist to test your explanation. Checks apply to this visit.
Try before revealing
Hint 1
Begin with n components, not with the number of observed endpoint labels.
Hint 2
For each undirected pair, find both representatives.
Hint 3
Attach smaller to larger only when roots differ, decrementing once.
Derive the solution
Reveal the baseline, optimized reasoning, and Java code
Build adjacency lists and count BFS starts
Allocate an undirected adjacency list for all n vertices, including isolated labels. Add both directions of each occurrence, then start a mark-on-enqueue BFS at every unseen vertex. Each start is one component. This compiling baseline is linear in input size but stores the full adjacency representation.
Improve the baseline
Initialize every declared vertex
parent[v]=v, size[v]=1, and components=n, even when the edge list is empty. Initializing only observed labels loses isolated components.
Find roots while shortening paths
Use iterative grandparent rewiring. For each pair, compare the resulting representatives rather than endpoint IDs or immediate parent entries.
Attach roots and update count exactly once
For distinct roots, attach the smaller tree to the larger, combine root sizes, and decrement the count. Equal roots leave the count unchanged, including self-loops, duplicate edges, and redundant edges within a cycle.
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.
Each union matches one reachability update
Before an insertion, sets equal earlier graph components. An edge between different sets creates exactly one larger component; an edge within a set does not change reachability. Induction preserves equivalence with the full processed graph.
Count and representation independence
The n singleton sets lose one component per successful union, so components=n−successfulMerges equals the number of roots and the true graph component count. Different valid union orders or root choices may change parent arrays but cannot change that partition or result.
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 void validate(int n,int[][] edges) {
if(n<0)throw new IllegalArgumentException("negative vertex count");Objects.requireNonNull(edges,"edges");for(int[] edge:edges)if(edge==null||edge.length!=2||edge[0]<0||edge[0]>=n||edge[1]<0||edge[1]>=n)throw new IllegalArgumentException("invalid endpoint pair");
}
public static int countComponents(int n,int[][] edges) {
validate(n,edges);Dsu dsu=new Dsu(n);for(int[] edge:edges)dsu.union(edge[0],edge[1]);return dsu.components;
}
public static int baseline(int n,int[][] edges) {
validate(n,edges);List<List<Integer>> graph=new ArrayList<>();for(int v=0;v<n;v++)graph.add(new ArrayList<>());for(int[] edge:edges){graph.get(edge[0]).add(edge[1]);graph.get(edge[1]).add(edge[0]);}
boolean[] seen=new boolean[n];ArrayDeque<Integer> queue=new ArrayDeque<>();int count=0;for(int start=0;start<n;start++)if(!seen[start]){count++;seen[start]=true;queue.addLast(start);while(!queue.isEmpty()){int v=queue.removeFirst();for(int next:graph.get(v))if(!seen[next]){seen[next]=true;queue.addLast(next);}}}return count;
}
}
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.
Attach roots, never arbitrary endpoints
Linking a nonroot can detach only part of an old set or break the size invariant. Find first, swap root variables only when needed, then attach the smaller root.
Size balance and compression solve different problems
Size-based linking bounds uncompressed tree depth by logarithmic growth: a vertex’s component at least doubles whenever its root is attached. Halving improves repeated finds and yields the stronger amortized sequence bound.
The array forest does not store graph topology
Root links can connect representatives that were never original edge endpoints together. DSU answers membership and counts, not shortest paths, traversal order, or direct adjacency.
Complexity
For V=n and E occurrences, main time is O(V+E·α(V+1)+1), with O(V+1) auxiliary parent/size storage and one int output. It need not retain all edges in a new adjacency list. The BFS baseline is O(V+E+1) time and O(V+E+1) auxiliary space. DSU is not a claim of a better static time bound than BFS.
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(V+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
Two components after a sparse chain
Input: {"n":5,"edges":[[0,1],[1,2],[3,4]]} · Undirected component count: 2
Step 1 of 12: 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: (0, 1)
- 1: (1, 2)
- 2: (3, 4)
Every declared label 0..4 exists, including isolated vertices absent from the edge stream.
Parent forest — arrows are implementation links, not original graph edges
- 0parent → 0 (root)root size 1
- 1parent → 1 (root)root size 1
- 2parent → 2 (root)root size 1
- 3parent → 3 (root)root size 1
- 4parent → 4 (root)root size 1
Component count: 5. Root choices need not be the smallest member.
Current partition — members grouped by representative
- root 0: {0}
- root 1: {1}
- root 2: {2}
- root 3: {3}
- root 4: {4}
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 | {"n":5,"edges":[[0,1],[1,2],[3,4]]} |
| parent | [0,1,2,3,4] |
| size | [1,1,1,1,1] |
| components | 5 |
| 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 void validate(int n,int[][] edges) { 10 if(n<0)throw new IllegalArgumentException("negative vertex count");Objects.requireNonNull(edges,"edges");for(int[] edge:edges)if(edge==null||edge.length!=2||edge[0]<0||edge[0]>=n||edge[1]<0||edge[1]>=n)throw new IllegalArgumentException("invalid endpoint pair"); 11 } 12 public static int countComponents(int n,int[][] edges) { 13 validate(n,edges);Dsu dsu=new Dsu(n);for(int[] edge:edges)dsu.union(edge[0],edge[1]);return dsu.components; 14 } 15 public static int baseline(int n,int[][] edges) { 16 validate(n,edges);List<List<Integer>> graph=new ArrayList<>();for(int v=0;v<n;v++)graph.add(new ArrayList<>());for(int[] edge:edges){graph.get(edge[0]).add(edge[1]);graph.get(edge[1]).add(edge[0]);} 17 boolean[] seen=new boolean[n];ArrayDeque<Integer> queue=new ArrayDeque<>();int count=0;for(int start=0;start<n;start++)if(!seen[start]){count++;seen[start]=true;queue.addLast(start);while(!queue.isEmpty()){int v=queue.removeFirst();for(int next:graph.get(v))if(!seen[next]){seen[next]=true;queue.addLast(next);}}}return count; 18 } 19 } 20
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
{"n":5,"edges":[[0,1],[1,2],[3,4]]}- parent
[0,1,2,3,4]- size
[1,1,1,1,1]- components
5- 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
{"n":5,"edges":[[0,1],[1,2],[3,4]]}- parent
[0,1,2,3,4]- size
[1,1,1,1,1]- components
5- processed
[]- index
0- edge
[0,1]- 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
{"n":5,"edges":[[0,1],[1,2],[3,4]]}- parent
[0,1,2,3,4]- size
[1,1,1,1,1]- components
5- processed
[]- index
0- edge
[0,1]- 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
{"n":5,"edges":[[0,1],[1,2],[3,4]]}- parent
[0,0,2,3,4]- size
[2,1,1,1,1]- components
4- processed
[{"a":0,"b":1,"merged":true}]- index
0- edge
[0,1]- 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
{"n":5,"edges":[[0,1],[1,2],[3,4]]}- parent
[0,0,2,3,4]- size
[2,1,1,1,1]- components
4- processed
[{"a":0,"b":1,"merged":true}]- index
1- edge
[1,2]- 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
{"n":5,"edges":[[0,1],[1,2],[3,4]]}- parent
[0,0,2,3,4]- size
[2,1,1,1,1]- components
4- processed
[{"a":0,"b":1,"merged":true}]- index
1- edge
[1,2]- 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
{"n":5,"edges":[[0,1],[1,2],[3,4]]}- parent
[0,0,0,3,4]- size
[3,1,1,1,1]- components
3- processed
[{"a":0,"b":1,"merged":true},{"a":1,"b":2,"merged":true}]- index
1- edge
[1,2]- 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
{"n":5,"edges":[[0,1],[1,2],[3,4]]}- parent
[0,0,0,3,4]- size
[3,1,1,1,1]- components
3- processed
[{"a":0,"b":1,"merged":true},{"a":1,"b":2,"merged":true}]- index
2- edge
[3,4]- answer
[]- phase
"find"- current
3- role
"a"- path
[3]- changes
[]- root
3
- 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
{"n":5,"edges":[[0,1],[1,2],[3,4]]}- parent
[0,0,0,3,4]- size
[3,1,1,1,1]- components
3- processed
[{"a":0,"b":1,"merged":true},{"a":1,"b":2,"merged":true}]- index
2- edge
[3,4]- answer
[]- phase
"find"- current
4- role
"b"- path
[4]- changes
[]- root
4
- 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
{"n":5,"edges":[[0,1],[1,2],[3,4]]}- parent
[0,0,0,3,3]- size
[3,1,1,2,1]- components
2- processed
[{"a":0,"b":1,"merged":true},{"a":1,"b":2,"merged":true},{"a":3,"b":4,"merged":true}]- index
2- edge
[3,4]- answer
[]- phase
"union"- current
3- rootA
3- rootB
4- kept
3- attached
4- 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
{"n":5,"edges":[[0,1],[1,2],[3,4]]}- parent
[0,0,0,3,3]- size
[3,1,1,2,1]- components
2- processed
[{"a":0,"b":1,"merged":true},{"a":1,"b":2,"merged":true},{"a":3,"b":4,"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
2
Balanced trees expose nontrivial path halving
Input: {"n":8,"edges":[[0,1],[2,3],[4,5],[6,7],[0,2],[4,6],[0,4],[7,3]]} · Undirected component count: 1
Step 1 of 27: 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: (0, 1)
- 1: (2, 3)
- 2: (4, 5)
- 3: (6, 7)
- 4: (0, 2)
- 5: (4, 6)
- 6: (0, 4)
- 7: (7, 3)
Every declared label 0..7 exists, including isolated vertices absent from the edge stream.
Parent forest — arrows are implementation links, not original graph edges
- 0parent → 0 (root)root size 1
- 1parent → 1 (root)root size 1
- 2parent → 2 (root)root size 1
- 3parent → 3 (root)root size 1
- 4parent → 4 (root)root size 1
- 5parent → 5 (root)root size 1
- 6parent → 6 (root)root size 1
- 7parent → 7 (root)root size 1
Component count: 8. Root choices need not be the smallest member.
Current partition — members grouped by representative
- root 0: {0}
- root 1: {1}
- root 2: {2}
- root 3: {3}
- root 4: {4}
- root 5: {5}
- root 6: {6}
- root 7: {7}
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 | {"n":8,"edges":[[0,1],[2,3],[4,5],[6,7],[0,2],[4,6],[0,4],[7,3]]} |
| parent | [0,1,2,3,4,5,6,7] |
| size | [1,1,1,1,1,1,1,1] |
| components | 8 |
| 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 void validate(int n,int[][] edges) { 10 if(n<0)throw new IllegalArgumentException("negative vertex count");Objects.requireNonNull(edges,"edges");for(int[] edge:edges)if(edge==null||edge.length!=2||edge[0]<0||edge[0]>=n||edge[1]<0||edge[1]>=n)throw new IllegalArgumentException("invalid endpoint pair"); 11 } 12 public static int countComponents(int n,int[][] edges) { 13 validate(n,edges);Dsu dsu=new Dsu(n);for(int[] edge:edges)dsu.union(edge[0],edge[1]);return dsu.components; 14 } 15 public static int baseline(int n,int[][] edges) { 16 validate(n,edges);List<List<Integer>> graph=new ArrayList<>();for(int v=0;v<n;v++)graph.add(new ArrayList<>());for(int[] edge:edges){graph.get(edge[0]).add(edge[1]);graph.get(edge[1]).add(edge[0]);} 17 boolean[] seen=new boolean[n];ArrayDeque<Integer> queue=new ArrayDeque<>();int count=0;for(int start=0;start<n;start++)if(!seen[start]){count++;seen[start]=true;queue.addLast(start);while(!queue.isEmpty()){int v=queue.removeFirst();for(int next:graph.get(v))if(!seen[next]){seen[next]=true;queue.addLast(next);}}}return count; 18 } 19 } 20
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
{"n":8,"edges":[[0,1],[2,3],[4,5],[6,7],[0,2],[4,6],[0,4],[7,3]]}- parent
[0,1,2,3,4,5,6,7]- size
[1,1,1,1,1,1,1,1]- components
8- 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
{"n":8,"edges":[[0,1],[2,3],[4,5],[6,7],[0,2],[4,6],[0,4],[7,3]]}- parent
[0,1,2,3,4,5,6,7]- size
[1,1,1,1,1,1,1,1]- components
8- processed
[]- index
0- edge
[0,1]- 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
{"n":8,"edges":[[0,1],[2,3],[4,5],[6,7],[0,2],[4,6],[0,4],[7,3]]}- parent
[0,1,2,3,4,5,6,7]- size
[1,1,1,1,1,1,1,1]- components
8- processed
[]- index
0- edge
[0,1]- 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
{"n":8,"edges":[[0,1],[2,3],[4,5],[6,7],[0,2],[4,6],[0,4],[7,3]]}- parent
[0,0,2,3,4,5,6,7]- size
[2,1,1,1,1,1,1,1]- components
7- processed
[{"a":0,"b":1,"merged":true}]- index
0- edge
[0,1]- 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
{"n":8,"edges":[[0,1],[2,3],[4,5],[6,7],[0,2],[4,6],[0,4],[7,3]]}- parent
[0,0,2,3,4,5,6,7]- size
[2,1,1,1,1,1,1,1]- components
7- processed
[{"a":0,"b":1,"merged":true}]- index
1- edge
[2,3]- 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
{"n":8,"edges":[[0,1],[2,3],[4,5],[6,7],[0,2],[4,6],[0,4],[7,3]]}- parent
[0,0,2,3,4,5,6,7]- size
[2,1,1,1,1,1,1,1]- components
7- processed
[{"a":0,"b":1,"merged":true}]- index
1- edge
[2,3]- 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
{"n":8,"edges":[[0,1],[2,3],[4,5],[6,7],[0,2],[4,6],[0,4],[7,3]]}- parent
[0,0,2,2,4,5,6,7]- size
[2,1,2,1,1,1,1,1]- components
6- processed
[{"a":0,"b":1,"merged":true},{"a":2,"b":3,"merged":true}]- index
1- edge
[2,3]- 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
{"n":8,"edges":[[0,1],[2,3],[4,5],[6,7],[0,2],[4,6],[0,4],[7,3]]}- parent
[0,0,2,2,4,5,6,7]- size
[2,1,2,1,1,1,1,1]- components
6- processed
[{"a":0,"b":1,"merged":true},{"a":2,"b":3,"merged":true}]- index
2- edge
[4,5]- answer
[]- phase
"find"- current
4- role
"a"- path
[4]- changes
[]- root
4
- 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
{"n":8,"edges":[[0,1],[2,3],[4,5],[6,7],[0,2],[4,6],[0,4],[7,3]]}- parent
[0,0,2,2,4,5,6,7]- size
[2,1,2,1,1,1,1,1]- components
6- processed
[{"a":0,"b":1,"merged":true},{"a":2,"b":3,"merged":true}]- index
2- edge
[4,5]- answer
[]- phase
"find"- current
5- role
"b"- path
[5]- changes
[]- root
5
- 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
{"n":8,"edges":[[0,1],[2,3],[4,5],[6,7],[0,2],[4,6],[0,4],[7,3]]}- parent
[0,0,2,2,4,4,6,7]- size
[2,1,2,1,2,1,1,1]- components
5- processed
[{"a":0,"b":1,"merged":true},{"a":2,"b":3,"merged":true},{"a":4,"b":5,"merged":true}]- index
2- edge
[4,5]- answer
[]- phase
"union"- current
4- rootA
4- rootB
5- kept
4- attached
5- 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
{"n":8,"edges":[[0,1],[2,3],[4,5],[6,7],[0,2],[4,6],[0,4],[7,3]]}- parent
[0,0,2,2,4,4,6,7]- size
[2,1,2,1,2,1,1,1]- components
5- processed
[{"a":0,"b":1,"merged":true},{"a":2,"b":3,"merged":true},{"a":4,"b":5,"merged":true}]- index
3- edge
[6,7]- answer
[]- phase
"find"- current
6- role
"a"- path
[6]- changes
[]- root
6
- 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
{"n":8,"edges":[[0,1],[2,3],[4,5],[6,7],[0,2],[4,6],[0,4],[7,3]]}- parent
[0,0,2,2,4,4,6,7]- size
[2,1,2,1,2,1,1,1]- components
5- processed
[{"a":0,"b":1,"merged":true},{"a":2,"b":3,"merged":true},{"a":4,"b":5,"merged":true}]- index
3- edge
[6,7]- answer
[]- phase
"find"- current
7- role
"b"- path
[7]- changes
[]- root
7
- 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
{"n":8,"edges":[[0,1],[2,3],[4,5],[6,7],[0,2],[4,6],[0,4],[7,3]]}- parent
[0,0,2,2,4,4,6,6]- size
[2,1,2,1,2,1,2,1]- components
4- processed
[{"a":0,"b":1,"merged":true},{"a":2,"b":3,"merged":true},{"a":4,"b":5,"merged":true},{"a":6,"b":7,"merged":true}]- index
3- edge
[6,7]- answer
[]- phase
"union"- current
6- rootA
6- rootB
7- kept
6- attached
7- 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
{"n":8,"edges":[[0,1],[2,3],[4,5],[6,7],[0,2],[4,6],[0,4],[7,3]]}- parent
[0,0,2,2,4,4,6,6]- size
[2,1,2,1,2,1,2,1]- components
4- processed
[{"a":0,"b":1,"merged":true},{"a":2,"b":3,"merged":true},{"a":4,"b":5,"merged":true},{"a":6,"b":7,"merged":true}]- index
4- edge
[0,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
{"n":8,"edges":[[0,1],[2,3],[4,5],[6,7],[0,2],[4,6],[0,4],[7,3]]}- parent
[0,0,2,2,4,4,6,6]- size
[2,1,2,1,2,1,2,1]- components
4- processed
[{"a":0,"b":1,"merged":true},{"a":2,"b":3,"merged":true},{"a":4,"b":5,"merged":true},{"a":6,"b":7,"merged":true}]- index
4- edge
[0,2]- 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
{"n":8,"edges":[[0,1],[2,3],[4,5],[6,7],[0,2],[4,6],[0,4],[7,3]]}- parent
[0,0,0,2,4,4,6,6]- size
[4,1,2,1,2,1,2,1]- components
3- processed
[{"a":0,"b":1,"merged":true},{"a":2,"b":3,"merged":true},{"a":4,"b":5,"merged":true},{"a":6,"b":7,"merged":true},{"a":0,"b":2,"merged":true}]- index
4- edge
[0,2]- 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
{"n":8,"edges":[[0,1],[2,3],[4,5],[6,7],[0,2],[4,6],[0,4],[7,3]]}- parent
[0,0,0,2,4,4,6,6]- size
[4,1,2,1,2,1,2,1]- components
3- processed
[{"a":0,"b":1,"merged":true},{"a":2,"b":3,"merged":true},{"a":4,"b":5,"merged":true},{"a":6,"b":7,"merged":true},{"a":0,"b":2,"merged":true}]- index
5- edge
[4,6]- answer
[]- phase
"find"- current
4- role
"a"- path
[4]- changes
[]- root
4
- 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
{"n":8,"edges":[[0,1],[2,3],[4,5],[6,7],[0,2],[4,6],[0,4],[7,3]]}- parent
[0,0,0,2,4,4,6,6]- size
[4,1,2,1,2,1,2,1]- components
3- processed
[{"a":0,"b":1,"merged":true},{"a":2,"b":3,"merged":true},{"a":4,"b":5,"merged":true},{"a":6,"b":7,"merged":true},{"a":0,"b":2,"merged":true}]- index
5- edge
[4,6]- answer
[]- phase
"find"- current
6- role
"b"- path
[6]- changes
[]- root
6
- 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
{"n":8,"edges":[[0,1],[2,3],[4,5],[6,7],[0,2],[4,6],[0,4],[7,3]]}- parent
[0,0,0,2,4,4,4,6]- size
[4,1,2,1,4,1,2,1]- components
2- processed
[{"a":0,"b":1,"merged":true},{"a":2,"b":3,"merged":true},{"a":4,"b":5,"merged":true},{"a":6,"b":7,"merged":true},{"a":0,"b":2,"merged":true},{"a":4,"b":6,"merged":true}]- index
5- edge
[4,6]- answer
[]- phase
"union"- current
4- rootA
4- rootB
6- kept
4- attached
6- 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
{"n":8,"edges":[[0,1],[2,3],[4,5],[6,7],[0,2],[4,6],[0,4],[7,3]]}- parent
[0,0,0,2,4,4,4,6]- size
[4,1,2,1,4,1,2,1]- components
2- processed
[{"a":0,"b":1,"merged":true},{"a":2,"b":3,"merged":true},{"a":4,"b":5,"merged":true},{"a":6,"b":7,"merged":true},{"a":0,"b":2,"merged":true},{"a":4,"b":6,"merged":true}]- index
6- edge
[0,4]- 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
{"n":8,"edges":[[0,1],[2,3],[4,5],[6,7],[0,2],[4,6],[0,4],[7,3]]}- parent
[0,0,0,2,4,4,4,6]- size
[4,1,2,1,4,1,2,1]- components
2- processed
[{"a":0,"b":1,"merged":true},{"a":2,"b":3,"merged":true},{"a":4,"b":5,"merged":true},{"a":6,"b":7,"merged":true},{"a":0,"b":2,"merged":true},{"a":4,"b":6,"merged":true}]- index
6- edge
[0,4]- answer
[]- phase
"find"- current
4- role
"b"- path
[4]- changes
[]- root
4
- 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
{"n":8,"edges":[[0,1],[2,3],[4,5],[6,7],[0,2],[4,6],[0,4],[7,3]]}- parent
[0,0,0,2,0,4,4,6]- size
[8,1,2,1,4,1,2,1]- components
1- processed
[{"a":0,"b":1,"merged":true},{"a":2,"b":3,"merged":true},{"a":4,"b":5,"merged":true},{"a":6,"b":7,"merged":true},{"a":0,"b":2,"merged":true},{"a":4,"b":6,"merged":true},{"a":0,"b":4,"merged":true}]- index
6- edge
[0,4]- answer
[]- phase
"union"- current
0- rootA
0- rootB
4- kept
0- attached
4- 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
{"n":8,"edges":[[0,1],[2,3],[4,5],[6,7],[0,2],[4,6],[0,4],[7,3]]}- parent
[0,0,0,2,0,4,4,4]- size
[8,1,2,1,4,1,2,1]- components
1- processed
[{"a":0,"b":1,"merged":true},{"a":2,"b":3,"merged":true},{"a":4,"b":5,"merged":true},{"a":6,"b":7,"merged":true},{"a":0,"b":2,"merged":true},{"a":4,"b":6,"merged":true},{"a":0,"b":4,"merged":true}]- index
7- edge
[7,3]- answer
[]- phase
"find"- current
7- role
"a"- path
[7,4,0]- changes
[{"node":7,"before":6,"after":4},{"node":4,"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
{"n":8,"edges":[[0,1],[2,3],[4,5],[6,7],[0,2],[4,6],[0,4],[7,3]]}- parent
[0,0,0,0,0,4,4,4]- size
[8,1,2,1,4,1,2,1]- components
1- processed
[{"a":0,"b":1,"merged":true},{"a":2,"b":3,"merged":true},{"a":4,"b":5,"merged":true},{"a":6,"b":7,"merged":true},{"a":0,"b":2,"merged":true},{"a":4,"b":6,"merged":true},{"a":0,"b":4,"merged":true}]- index
7- edge
[7,3]- 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
{"n":8,"edges":[[0,1],[2,3],[4,5],[6,7],[0,2],[4,6],[0,4],[7,3]]}- parent
[0,0,0,0,0,4,4,4]- size
[8,1,2,1,4,1,2,1]- components
1- processed
[{"a":0,"b":1,"merged":true},{"a":2,"b":3,"merged":true},{"a":4,"b":5,"merged":true},{"a":6,"b":7,"merged":true},{"a":0,"b":2,"merged":true},{"a":4,"b":6,"merged":true},{"a":0,"b":4,"merged":true},{"a":7,"b":3,"merged":false}]- index
7- edge
[7,3]- answer
[]- phase
"same-set"- current
7- rootA
0- rootB
0- kept
0- attached
null- merged
false
- 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
{"n":8,"edges":[[0,1],[2,3],[4,5],[6,7],[0,2],[4,6],[0,4],[7,3]]}- parent
[0,0,0,0,0,4,4,4]- size
[8,1,2,1,4,1,2,1]- components
1- processed
[{"a":0,"b":1,"merged":true},{"a":2,"b":3,"merged":true},{"a":4,"b":5,"merged":true},{"a":6,"b":7,"merged":true},{"a":0,"b":2,"merged":true},{"a":4,"b":6,"merged":true},{"a":0,"b":4,"merged":true},{"a":7,"b":3,"merged":false}]- 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
1
Duplicates and self-loops leave the count unchanged
Input: {"n":4,"edges":[[0,1],[1,0],[2,2]]} · Undirected component count: 3
Step 1 of 12: 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: (0, 1)
- 1: (1, 0)
- 2: (2, 2)
Every declared label 0..3 exists, including isolated vertices absent from the edge stream.
Parent forest — arrows are implementation links, not original graph edges
- 0parent → 0 (root)root size 1
- 1parent → 1 (root)root size 1
- 2parent → 2 (root)root size 1
- 3parent → 3 (root)root size 1
Component count: 4. Root choices need not be the smallest member.
Current partition — members grouped by representative
- root 0: {0}
- root 1: {1}
- root 2: {2}
- root 3: {3}
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 | {"n":4,"edges":[[0,1],[1,0],[2,2]]} |
| 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 void validate(int n,int[][] edges) { 10 if(n<0)throw new IllegalArgumentException("negative vertex count");Objects.requireNonNull(edges,"edges");for(int[] edge:edges)if(edge==null||edge.length!=2||edge[0]<0||edge[0]>=n||edge[1]<0||edge[1]>=n)throw new IllegalArgumentException("invalid endpoint pair"); 11 } 12 public static int countComponents(int n,int[][] edges) { 13 validate(n,edges);Dsu dsu=new Dsu(n);for(int[] edge:edges)dsu.union(edge[0],edge[1]);return dsu.components; 14 } 15 public static int baseline(int n,int[][] edges) { 16 validate(n,edges);List<List<Integer>> graph=new ArrayList<>();for(int v=0;v<n;v++)graph.add(new ArrayList<>());for(int[] edge:edges){graph.get(edge[0]).add(edge[1]);graph.get(edge[1]).add(edge[0]);} 17 boolean[] seen=new boolean[n];ArrayDeque<Integer> queue=new ArrayDeque<>();int count=0;for(int start=0;start<n;start++)if(!seen[start]){count++;seen[start]=true;queue.addLast(start);while(!queue.isEmpty()){int v=queue.removeFirst();for(int next:graph.get(v))if(!seen[next]){seen[next]=true;queue.addLast(next);}}}return count; 18 } 19 } 20
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
{"n":4,"edges":[[0,1],[1,0],[2,2]]}- 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
{"n":4,"edges":[[0,1],[1,0],[2,2]]}- parent
[0,1,2,3]- size
[1,1,1,1]- components
4- processed
[]- index
0- edge
[0,1]- 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
{"n":4,"edges":[[0,1],[1,0],[2,2]]}- parent
[0,1,2,3]- size
[1,1,1,1]- components
4- processed
[]- index
0- edge
[0,1]- 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
{"n":4,"edges":[[0,1],[1,0],[2,2]]}- parent
[0,0,2,3]- size
[2,1,1,1]- components
3- processed
[{"a":0,"b":1,"merged":true}]- index
0- edge
[0,1]- 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
{"n":4,"edges":[[0,1],[1,0],[2,2]]}- parent
[0,0,2,3]- size
[2,1,1,1]- components
3- processed
[{"a":0,"b":1,"merged":true}]- index
1- edge
[1,0]- 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
{"n":4,"edges":[[0,1],[1,0],[2,2]]}- parent
[0,0,2,3]- size
[2,1,1,1]- components
3- processed
[{"a":0,"b":1,"merged":true}]- index
1- edge
[1,0]- 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
{"n":4,"edges":[[0,1],[1,0],[2,2]]}- parent
[0,0,2,3]- size
[2,1,1,1]- components
3- processed
[{"a":0,"b":1,"merged":true},{"a":1,"b":0,"merged":false}]- index
1- edge
[1,0]- answer
[]- phase
"same-set"- current
1- rootA
0- rootB
0- kept
0- attached
null- merged
false
- 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
{"n":4,"edges":[[0,1],[1,0],[2,2]]}- parent
[0,0,2,3]- size
[2,1,1,1]- components
3- processed
[{"a":0,"b":1,"merged":true},{"a":1,"b":0,"merged":false}]- index
2- edge
[2,2]- 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
{"n":4,"edges":[[0,1],[1,0],[2,2]]}- parent
[0,0,2,3]- size
[2,1,1,1]- components
3- processed
[{"a":0,"b":1,"merged":true},{"a":1,"b":0,"merged":false}]- index
2- edge
[2,2]- answer
[]- phase
"find"- current
2- role
"b"- path
[2]- changes
[]- root
2
- 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
{"n":4,"edges":[[0,1],[1,0],[2,2]]}- parent
[0,0,2,3]- size
[2,1,1,1]- components
3- processed
[{"a":0,"b":1,"merged":true},{"a":1,"b":0,"merged":false},{"a":2,"b":2,"merged":false}]- index
2- edge
[2,2]- answer
[]- phase
"same-set"- current
2- rootA
2- rootB
2- kept
2- attached
null- merged
false
- 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
{"n":4,"edges":[[0,1],[1,0],[2,2]]}- parent
[0,0,2,3]- size
[2,1,1,1]- components
3- processed
[{"a":0,"b":1,"merged":true},{"a":1,"b":0,"merged":false},{"a":2,"b":2,"merged":false}]- 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
3
All declared vertices can be isolated
Input: {"n":4,"edges":[]} · Undirected component count: 4
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.
Every declared label 0..3 exists, including isolated vertices absent from the edge stream.
Parent forest — arrows are implementation links, not original graph edges
- 0parent → 0 (root)root size 1
- 1parent → 1 (root)root size 1
- 2parent → 2 (root)root size 1
- 3parent → 3 (root)root size 1
Component count: 4. Root choices need not be the smallest member.
Current partition — members grouped by representative
- root 0: {0}
- root 1: {1}
- root 2: {2}
- root 3: {3}
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 | {"n":4,"edges":[]} |
| 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 void validate(int n,int[][] edges) { 10 if(n<0)throw new IllegalArgumentException("negative vertex count");Objects.requireNonNull(edges,"edges");for(int[] edge:edges)if(edge==null||edge.length!=2||edge[0]<0||edge[0]>=n||edge[1]<0||edge[1]>=n)throw new IllegalArgumentException("invalid endpoint pair"); 11 } 12 public static int countComponents(int n,int[][] edges) { 13 validate(n,edges);Dsu dsu=new Dsu(n);for(int[] edge:edges)dsu.union(edge[0],edge[1]);return dsu.components; 14 } 15 public static int baseline(int n,int[][] edges) { 16 validate(n,edges);List<List<Integer>> graph=new ArrayList<>();for(int v=0;v<n;v++)graph.add(new ArrayList<>());for(int[] edge:edges){graph.get(edge[0]).add(edge[1]);graph.get(edge[1]).add(edge[0]);} 17 boolean[] seen=new boolean[n];ArrayDeque<Integer> queue=new ArrayDeque<>();int count=0;for(int start=0;start<n;start++)if(!seen[start]){count++;seen[start]=true;queue.addLast(start);while(!queue.isEmpty()){int v=queue.removeFirst();for(int next:graph.get(v))if(!seen[next]){seen[next]=true;queue.addLast(next);}}}return count; 18 } 19 } 20
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
{"n":4,"edges":[]}- parent
[0,1,2,3]- size
[1,1,1,1]- components
4- 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
{"n":4,"edges":[]}- parent
[0,1,2,3]- size
[1,1,1,1]- components
4- 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
4
Empty vertex universe
Input: {"n":0,"edges":[]} · Undirected component count: 0
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.
The declared vertex universe is empty.
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.
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 | {"n":0,"edges":[]} |
| 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 void validate(int n,int[][] edges) { 10 if(n<0)throw new IllegalArgumentException("negative vertex count");Objects.requireNonNull(edges,"edges");for(int[] edge:edges)if(edge==null||edge.length!=2||edge[0]<0||edge[0]>=n||edge[1]<0||edge[1]>=n)throw new IllegalArgumentException("invalid endpoint pair"); 11 } 12 public static int countComponents(int n,int[][] edges) { 13 validate(n,edges);Dsu dsu=new Dsu(n);for(int[] edge:edges)dsu.union(edge[0],edge[1]);return dsu.components; 14 } 15 public static int baseline(int n,int[][] edges) { 16 validate(n,edges);List<List<Integer>> graph=new ArrayList<>();for(int v=0;v<n;v++)graph.add(new ArrayList<>());for(int[] edge:edges){graph.get(edge[0]).add(edge[1]);graph.get(edge[1]).add(edge[0]);} 17 boolean[] seen=new boolean[n];ArrayDeque<Integer> queue=new ArrayDeque<>();int count=0;for(int start=0;start<n;start++)if(!seen[start]){count++;seen[start]=true;queue.addLast(start);while(!queue.isEmpty()){int v=queue.removeFirst();for(int next:graph.get(v))if(!seen[next]){seen[next]=true;queue.addLast(next);}}}return count; 18 } 19 } 20
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
{"n":0,"edges":[]}- 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
{"n":0,"edges":[]}- 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
0
Test the contract
Input:
All vertices isolated
Output:nExplicit universe matters.
Input:
Triangle, self-loops, and reversed duplicates
Output:one decrement per actual component joinIdempotent connectivity effects.
Input:
Balanced unions followed by redundant queries
Output:same partition with shorter parent pathsCompression can occur without a successful merge.
Input:
Shared read-only edge rows
Output:unchanged source referencesOccurrence processing remains correct.
Input:
100,000 vertices and 200,000 occurrences
Output:correct count under duplicates/self-loopsDeclared sparse-graph boundary without recursive depth.
Common mistakes and counterexamples
Count only vertices appearing in edges
Counterexample: n=4 with no edges must return four.
Initialize all n singleton components.
Compare immediate parents instead of representatives
Counterexample: Two vertices can share a root through different intermediate parents.
Call find before testing membership.
Decrement for a self-loop or duplicate
Counterexample: After [0,1], processing [1,0] must not reduce the count again.
Only a distinct-root attachment reduces components.
Assume one find fully flattens the tree
Counterexample: Path halving can jump over intermediate nodes and retain some depth.
Follow the exact grandparent-rewrite algorithm; correctness depends on membership, not a star shape.
Follow-ups
Answer connectivity and component-size queries after each insertion.
Compare find(a)==find(b) and read size[find(a)]. Count query operations in the amortized bound and never read a nonroot size as current cardinality.
Handle deletions with offline rollback.
Record reversible root/size/count changes and process edge-active intervals with a time-segment structure. Ordinary path compression complicates rollback; use an explicit compatible design and analyze its costs separately.
Return a canonical component listing.
Group vertices by final roots, sort members if needed, then order components by a defined canonical key such as minimum member. A root ID is not itself a canonical key.