DSA-109 · FOCUSED PRACTICE
Number of Provinces
Core · Java 21 · Version 1 · editorial draft
Java reference and baseline verified on JDK 21: 69756 deterministic checks. Learner drafts are not executed.
Understand the problem
Given an undirected city-connectivity matrix, return the number of provinces, where a province is one connected component including transitive connections.
- connected is a nonnull square binary int matrix of n cities labeled 0..n-1, with diagonal ones and symmetric entries. n<=1000 is a size precondition. The empty matrix is valid and returns zero. Null outer input throws NullPointerException; null/ragged/non-square rows, nonbinary values, non-one diagonal, or asymmetry throw IllegalArgumentException before traversal.
- A one at [i][j] is an undirected direct connection. Transitive reachability, not row equality, defines a province. Every city exists even when it has only its diagonal one; do not count only vertices appearing in off-diagonal edges.
- Preserve all input values and row references. Shared input row objects are permitted when the matrix remains valid; vertices are city indices, not array identities. Return one int. The DSU is private and does not replace or rewrite the matrix.
Examples
Input:
[[1,1,0],[1,1,0],[0,0,1]]
Output:2Cities 0 and 1 form one province; city 2 is an isolated province.
Input:
[[1,1,0],[1,1,1],[0,1,1]]
Output:10 and 2 need no direct edge: the path through 1 joins all three cities.
Input:
[[1,1,1],[1,1,1],[1,1,1]]
Output:1After two successful joins, the remaining upper-triangle connection is within an existing set.
Before you start
- Undirected connectivity and transitive equivalence
- Representative forests, root sizes, and successful-union counts
Recognize the structure
The matrix represents an undirected equivalence closure to compute, not a directed dependency graph. DSU maintains the component partition as each direct edge is considered. Because input is dense, it still requires quadratic reading; BFS is already a strong static alternative rather than an asymptotically inferior baseline.
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 · 145/20,000 characters
Self-review
Use the checklist to test your explanation. Checks apply to this visit.
Try before revealing
Hint 1
Every city begins as a separate province, including isolated indices.
Hint 2
Process each undirected connection once using the upper triangle.
Hint 3
Join distinct roots by size and reduce the province count only on a successful union.
Derive the solution
Reveal the baseline, optimized reasoning, and Java code
Traverse each matrix component with BFS
Scan all city indices, starting a queue at each unseen city. Mark on enqueue and inspect all n columns of every popped city row. One start equals one province. This compiling baseline preserves the matrix, uses linear traversal state, and runs in quadratic time because all rows must be scanned.
Improve the baseline
Validate representation before computing
Check every row shape before any transpose access, then verify binary values, diagonal ones, and symmetry. This prevents malformed late rows from becoming accidental indexing/null failures.
Start with n singleton provinces
Initialize parent[v]=v, size[v]=1, and components=n. Scan only pairs r<c whose matrix entry is one; the diagonal is not a new connection and the lower triangle is duplicate evidence.
Count only joins between distinct roots
Find both roots with iterative halving. If they differ, attach the smaller root tree, add its root size, and decrement components once. If equal, membership and count stay unchanged even if find shortened a path.
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.
Processed-edge connectivity
Initially each city is isolated. A processed direct edge either joins two previously separate connected sets or connects vertices already reachable through earlier edges. Induction makes DSU membership exactly equal to the connected components of the processed undirected graph.
Final province count
All off-diagonal direct connections appear once in the upper triangle. Each successful union reduces the number of sets by one; no-op unions do not. Therefore the final root count is exactly the number of provinces, including untouched isolated cities.
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[][] connected) {
Objects.requireNonNull(connected,"connected");int n=connected.length;
for(int[] row:connected)if(row==null||row.length!=n)throw new IllegalArgumentException("expected square matrix");
for(int r=0;r<n;r++)for(int c=0;c<n;c++)if((connected[r][c]!=0&&connected[r][c]!=1)||(r==c&&connected[r][c]!=1)||connected[r][c]!=connected[c][r])throw new IllegalArgumentException("expected symmetric binary matrix with diagonal ones");
}
public static int provinces(int[][] connected) {
validate(connected);int n=connected.length;Dsu dsu=new Dsu(n);
for(int r=0;r<n;r++)for(int c=r+1;c<n;c++)if(connected[r][c]==1)dsu.union(r,c);
return dsu.components;
}
public static int baseline(int[][] connected) {
validate(connected);int n=connected.length,count=0;boolean[] seen=new boolean[n];ArrayDeque<Integer> queue=new ArrayDeque<>();
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=0;next<n;next++)if(connected[v][next]==1&&!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.
Size ties are a deterministic implementation rule
Equal-sized roots retain the first root argument. This controls walkthrough parent arrays, but the representative need not be the smallest label and does not affect the province count.
Dense input dominates discovery cost
Skipping the lower triangle avoids duplicate union attempts, but full validation and upper-triangle discovery still read Θ(n²) entries. Do not claim an adjacency-list O(V+E) bound while ignoring this representation.
Complexity
Let V=n and M be the number of upper-triangle ones. Main time is O(V²+M·α(V+1)+1); auxiliary parent/size arrays use O(V+1), and output is one int. The BFS baseline is O(V²+1) time with O(V+1) queue/seen space. DSU is useful for maintaining partitions and incremental extensions, not an automatic speedup over matrix 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
One connected pair plus an isolated city
Input: [[1,1,0],[1,1,0],[0,0,1]] · Province count: 2
Step 1 of 6: 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.
Unchanged city matrix — highlighted symmetric connection
The diagonal records city self-membership. Only upper-triangle off-diagonal ones trigger union attempts; full validation still reads the matrix.
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
Component count: 3. Root choices need not be the smallest member.
Current partition — members grouped by representative
- root 0: {0}
- root 1: {1}
- root 2: {2}
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,1,0],[1,1,0],[0,0,1]] |
| 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 void validate(int[][] connected) { 10 Objects.requireNonNull(connected,"connected");int n=connected.length; 11 for(int[] row:connected)if(row==null||row.length!=n)throw new IllegalArgumentException("expected square matrix"); 12 for(int r=0;r<n;r++)for(int c=0;c<n;c++)if((connected[r][c]!=0&&connected[r][c]!=1)||(r==c&&connected[r][c]!=1)||connected[r][c]!=connected[c][r])throw new IllegalArgumentException("expected symmetric binary matrix with diagonal ones"); 13 } 14 public static int provinces(int[][] connected) { 15 validate(connected);int n=connected.length;Dsu dsu=new Dsu(n); 16 for(int r=0;r<n;r++)for(int c=r+1;c<n;c++)if(connected[r][c]==1)dsu.union(r,c); 17 return dsu.components; 18 } 19 public static int baseline(int[][] connected) { 20 validate(connected);int n=connected.length,count=0;boolean[] seen=new boolean[n];ArrayDeque<Integer> queue=new ArrayDeque<>(); 21 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=0;next<n;next++)if(connected[v][next]==1&&!seen[next]){seen[next]=true;queue.addLast(next);}}}return count; 22 } 23 } 24
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,1,0],[1,1,0],[0,0,1]]- 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,1,0],[1,1,0],[0,0,1]]- parent
[0,1,2]- size
[1,1,1]- components
3- 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
[[1,1,0],[1,1,0],[0,0,1]]- parent
[0,1,2]- size
[1,1,1]- components
3- 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
[[1,1,0],[1,1,0],[0,0,1]]- parent
[0,0,2]- size
[2,1,1]- components
2- 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
- All candidate connections have been considered.
The upper triangle avoids processing symmetric entries twice; matrix validation still reads quadratic input.
- input
[[1,1,0],[1,1,0],[0,0,1]]- parent
[0,0,2]- size
[2,1,1]- components
2- processed
[{"a":0,"b":1,"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
A triangle contains a no-op union
Input: [[1,1,1],[1,1,1],[1,1,1]] · Province count: 1
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.
Unchanged city matrix — highlighted symmetric connection
The diagonal records city self-membership. Only upper-triangle off-diagonal ones trigger union attempts; full validation still reads the matrix.
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
Component count: 3. Root choices need not be the smallest member.
Current partition — members grouped by representative
- root 0: {0}
- root 1: {1}
- root 2: {2}
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,1,1],[1,1,1],[1,1,1]] |
| 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 void validate(int[][] connected) { 10 Objects.requireNonNull(connected,"connected");int n=connected.length; 11 for(int[] row:connected)if(row==null||row.length!=n)throw new IllegalArgumentException("expected square matrix"); 12 for(int r=0;r<n;r++)for(int c=0;c<n;c++)if((connected[r][c]!=0&&connected[r][c]!=1)||(r==c&&connected[r][c]!=1)||connected[r][c]!=connected[c][r])throw new IllegalArgumentException("expected symmetric binary matrix with diagonal ones"); 13 } 14 public static int provinces(int[][] connected) { 15 validate(connected);int n=connected.length;Dsu dsu=new Dsu(n); 16 for(int r=0;r<n;r++)for(int c=r+1;c<n;c++)if(connected[r][c]==1)dsu.union(r,c); 17 return dsu.components; 18 } 19 public static int baseline(int[][] connected) { 20 validate(connected);int n=connected.length,count=0;boolean[] seen=new boolean[n];ArrayDeque<Integer> queue=new ArrayDeque<>(); 21 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=0;next<n;next++)if(connected[v][next]==1&&!seen[next]){seen[next]=true;queue.addLast(next);}}}return count; 22 } 23 } 24
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,1,1],[1,1,1],[1,1,1]]- 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,1,1],[1,1,1],[1,1,1]]- parent
[0,1,2]- size
[1,1,1]- components
3- 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
[[1,1,1],[1,1,1],[1,1,1]]- parent
[0,1,2]- size
[1,1,1]- components
3- 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
[[1,1,1],[1,1,1],[1,1,1]]- parent
[0,0,2]- size
[2,1,1]- components
2- 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
[[1,1,1],[1,1,1],[1,1,1]]- parent
[0,0,2]- size
[2,1,1]- components
2- processed
[{"a":0,"b":1,"merged":true}]- index
1- 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
[[1,1,1],[1,1,1],[1,1,1]]- parent
[0,0,2]- size
[2,1,1]- components
2- processed
[{"a":0,"b":1,"merged":true}]- index
1- 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
[[1,1,1],[1,1,1],[1,1,1]]- 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
[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
[[1,1,1],[1,1,1],[1,1,1]]- 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
[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
[[1,1,1],[1,1,1],[1,1,1]]- 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
[1,2]- 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,1,1],[1,1,1],[1,1,1]]- 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
[1,2]- answer
[]- phase
"same-set"- current
1- rootA
0- rootB
0- kept
0- attached
null- merged
false
- All candidate connections have been considered.
The upper triangle avoids processing symmetric entries twice; matrix validation still reads quadratic input.
- input
[[1,1,1],[1,1,1],[1,1,1]]- 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
[]
- 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
Diagonal-only cities stay separate
Input: [[1,0,0],[0,1,0],[0,0,1]] · Province count: 3
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.
Unchanged city matrix — highlighted symmetric connection
The diagonal records city self-membership. Only upper-triangle off-diagonal ones trigger union attempts; full validation still reads the matrix.
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
Component count: 3. Root choices need not be the smallest member.
Current partition — members grouped by representative
- root 0: {0}
- root 1: {1}
- root 2: {2}
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,0,0],[0,1,0],[0,0,1]] |
| 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 void validate(int[][] connected) { 10 Objects.requireNonNull(connected,"connected");int n=connected.length; 11 for(int[] row:connected)if(row==null||row.length!=n)throw new IllegalArgumentException("expected square matrix"); 12 for(int r=0;r<n;r++)for(int c=0;c<n;c++)if((connected[r][c]!=0&&connected[r][c]!=1)||(r==c&&connected[r][c]!=1)||connected[r][c]!=connected[c][r])throw new IllegalArgumentException("expected symmetric binary matrix with diagonal ones"); 13 } 14 public static int provinces(int[][] connected) { 15 validate(connected);int n=connected.length;Dsu dsu=new Dsu(n); 16 for(int r=0;r<n;r++)for(int c=r+1;c<n;c++)if(connected[r][c]==1)dsu.union(r,c); 17 return dsu.components; 18 } 19 public static int baseline(int[][] connected) { 20 validate(connected);int n=connected.length,count=0;boolean[] seen=new boolean[n];ArrayDeque<Integer> queue=new ArrayDeque<>(); 21 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=0;next<n;next++)if(connected[v][next]==1&&!seen[next]){seen[next]=true;queue.addLast(next);}}}return count; 22 } 23 } 24
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,0,0],[0,1,0],[0,0,1]]- parent
[0,1,2]- size
[1,1,1]- components
3- processed
[]- phase
"initial"- current
null
- All candidate connections have been considered.
The upper triangle avoids processing symmetric entries twice; matrix validation still reads quadratic input.
- input
[[1,0,0],[0,1,0],[0,0,1]]- parent
[0,1,2]- size
[1,1,1]- components
3- 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
3
Empty city universe
Input: [] · Province 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.
Unchanged city matrix — highlighted symmetric connection
The diagonal records city self-membership. Only upper-triangle off-diagonal ones trigger union attempts; full validation still reads the matrix.
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 | [] |
| 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[][] connected) { 10 Objects.requireNonNull(connected,"connected");int n=connected.length; 11 for(int[] row:connected)if(row==null||row.length!=n)throw new IllegalArgumentException("expected square matrix"); 12 for(int r=0;r<n;r++)for(int c=0;c<n;c++)if((connected[r][c]!=0&&connected[r][c]!=1)||(r==c&&connected[r][c]!=1)||connected[r][c]!=connected[c][r])throw new IllegalArgumentException("expected symmetric binary matrix with diagonal ones"); 13 } 14 public static int provinces(int[][] connected) { 15 validate(connected);int n=connected.length;Dsu dsu=new Dsu(n); 16 for(int r=0;r<n;r++)for(int c=r+1;c<n;c++)if(connected[r][c]==1)dsu.union(r,c); 17 return dsu.components; 18 } 19 public static int baseline(int[][] connected) { 20 validate(connected);int n=connected.length,count=0;boolean[] seen=new boolean[n];ArrayDeque<Integer> queue=new ArrayDeque<>(); 21 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=0;next<n;next++)if(connected[v][next]==1&&!seen[next]){seen[next]=true;queue.addLast(next);}}}return count; 22 } 23 } 24
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 upper triangle avoids processing symmetric entries twice; matrix validation still reads quadratic input.
- 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
0
Test the contract
Input:
Empty matrix
Output:0No city vertices.
Input:
Diagonal-only matrix
Output:nEvery city is an isolated component.
Input:
Transitive chain and triangle
Output:one component in eachIndirect paths and no-op joins.
Input:
Valid shared all-one row objects
Output:1 with unchanged row identitiesCity indices remain distinct vertices.
Input:
1000×1000 all-one matrix
Output:1Declared dense-input boundary and full validation cost.
Common mistakes and counterexamples
Count rows or direct neighbors
Counterexample: The chain 0—1—2 is one province although 0 has no direct link to 2.
Compute transitive component membership.
Decrement for every one
Counterexample: A triangle has three off-diagonal edges but only two successful joins.
Decrement only when representatives differ.
Read transpose entries before shape validation
Counterexample: A null later row can turn symmetry checking into an unintended NullPointerException.
Validate all row shapes first.
Treat size at every node as current
Counterexample: A former root retains an old size after attachment.
Read component sizes only at self-parent roots.
Follow-ups
Add connections incrementally.
Keep the private DSU between insertions and update the count only for successful joins. The matrix need not be rescanned for each query if the API instead accepts an insertion stream.
Return the actual provinces.
Find every vertex, group by representative, and define deterministic member/component ordering. Allocate independent output containers; root IDs alone are not canonical component names.
Delete a connection.
Ordinary DSU cannot split a component or recover which graph edges were essential. Consider offline reverse processing, rollback DSU without ordinary compression, or a different dynamic-connectivity scope.