DSA-109 · Count components while joining the upper triangle of an undirected matrix

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: 2
Cities 0 and 1 form one province; city 2 is an isolated province.
Input: [[1,1,0],[1,1,1],[0,1,1]]
Output: 1
0 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: 1
After 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.

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.

Provinces — matrix evidence and root membership

Phase: initial.

Unchanged city matrix — highlighted symmetric connection

110

001

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.

State after this step
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.

Provinces — matrix evidence and root membership

Phase: initial.

Unchanged city matrix — highlighted symmetric connection

111

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.

State after this step
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.

Provinces — matrix evidence and root membership

Phase: initial.

Unchanged city matrix — highlighted symmetric connection

100

010

001

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.

State after this step
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.

Provinces — matrix evidence and root membership

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.

State after this step
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: 0
No city vertices.
Input: Diagonal-only matrix
Output: n
Every city is an isolated component.
Input: Transitive chain and triangle
Output: one component in each
Indirect paths and no-op joins.
Input: Valid shared all-one row objects
Output: 1 with unchanged row identities
City indices remain distinct vertices.
Input: 1000×1000 all-one matrix
Output: 1
Declared 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.

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.

Approach, code, and test notes (20,000 characters maximum)

No unsaved text changes · 145/20,000 characters

Self-review

Can I prove root membership matches processed-edge reachability?Can I distinguish root sizes from stale nonroot values?Can I include the matrix-reading cost and explain when BFS is equally suitable?

Use the checklist to test your explanation. Checks apply to this visit.

Related foundations

Disjoint-set foundations: partitions, representatives, and ownership

Keep practicing

Open focused practice

AceYourInterviews · 2026-10-17 · Original teaching content and implementations authored for AceYourInterviews. Standard names do not imply external-platform parity or company-frequency claims.