Easy · DSU on Adjacency Matrix
Understand → Visualise → Practice.
An adjacency matrix describes direct city connections. Return the number of connected provinces.
Each 1 in the adjacency matrix links two cities. Union them; the number of distinct roots at the end is the number of provinces.
Each city is its own set.
For every pair i > j with connected[i][j] == 1, union them.
Return the number of distinct roots.
O(n² α(n)) time and O(n) space.
Counting the 1s in the matrix counts connections, not provinces.
Read the full guide first: Union-Find for Dynamic Connectivity.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.