Count the Islands of Connected Towns
Implement countComponents
There 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.
Example 1:
Input: adj = [[1,2],[0],[0],[4],[3],[],[]]
Output: 4
Example 2:
Input: adj = [[1],[0,2],[1]]
Output: 1
Example 3:
Input: adj = []
Output: 0
+ 13 hidden test cases run on Submit.
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
adj =