Count the Islands of Connected Towns
Solve this ProblemThere are n towns numbered 0 to n − 1, and some pairs of towns are joined by a road. The roads are given as an adjacency list: adj[i] is the list of towns that town i has a direct road to (each road appears in both towns' lists). Two towns belong to the same group if you can travel from one to the other along roads. Return the number of groups (the number of connected components of the graph); a town with no roads is a group of its own.
You can sweep labels along the roads until they settle, or use a union-find structure in which every successful merge of two groups lowers the count by one.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
0 ≤ n ≤ 100 towns, numbered 0 … n − 1; the graph is given as an adjacency list: adj[i] lists the towns that have a road to town i - ◆
Every road is listed in BOTH directions (if j is in adj[i], then i is in adj[j]); there are no roads from a town to itself, and a row can be empty - ◆
Two towns are in the same group when there is a chain of roads between them (a connected component). A town without roads forms a group on its own - ◆
Return the number of groups (connected components); 0 for an empty graph
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Keep Lowering Labels Along the Roads Until Nothing Changes
BruteGive every town its own number as a label. Sweep over all roads again and again: whenever a town has a neighbour with a smaller label, the town takes that smaller label. Labels flow along roads, and after enough sweeps every town of a group carries the smallest number in the group; the groups are then the towns whose label equals their own number. One sweep costs O(n + m), and a label can need up to n sweeps to cross a long chain of towns.
O(n · (n + m))O(n)1class Solution {
2 public int countComponents(int[][] adj) {
3 int n = adj.length;
4 int[] label = new int[n];
5 for (int i = 0; i < n; i++) label[i] = i;
6 boolean changed = true;
7 while (changed) {
8 changed = false;
9 for (int u = 0; u < n; u++) {
10 for (int v : adj[u]) {
11 if (label[v] < label[u]) {
12 label[u] = label[v];
13 changed = true;
14 }
15 }
16 }
17 }
18 int count = 0;
19 for (int i = 0; i < n; i++) {
20 if (label[i] == i) count++;
21 }
22 return count;
23 }
24}Optimal — Union-Find: Every Merge Removes One Group
OptimalStart with n groups, one per town, each town being its own "leader" (parent[i] = i). For every road (u, v): find the leaders of u and v (following parent links, and shortening the path as you go — "path halving"); if the leaders differ, the towns were in different groups, so join them by pointing one leader at the other and decrease the group count by one. If the leaders are equal, the road connects towns that are already together and changes nothing. After all roads, the counter is the number of groups. Nearly linear time; O(n) memory.
O((n + m) · α(n))O(n)1class Solution {
2 public int countComponents(int[][] adj) {
3 int n = adj.length;
4 int[] parent = new int[n];
5 for (int i = 0; i < n; i++) parent[i] = i;
6 int components = n;
7 for (int u = 0; u < n; u++) {
8 for (int v : adj[u]) {
9 int ru = find(parent, u);
10 int rv = find(parent, v);
11 if (ru != rv) {
12 parent[ru] = rv;
13 components--;
14 }
15 }
16 }
17 return components;
18 }
19
20 private int find(int[] parent, int x) {
21 while (parent[x] != x) {
22 parent[x] = parent[parent[x]];
23 x = parent[x];
24 }
25 return x;
26 }
27}