Problem Description
Given an undirected graph with V vertices. We say two vertices u and v belong to a single province if there is a path from u to v or v to u. Your task is to find the number of provinces.
Note: A province is a group of directly or indirectly connected cities and no other cities outside of the group.
Solution
We need to basically find the number of connected components in the given graph. This is similar to this post:
Number of Connected Components in an Undirected Graph
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
static int numProvinces(ArrayList<ArrayList<Integer>> adj, int V) {
//track visited nodes
boolean[] visited = new boolean[V];
//number of connected components
int count = 0;
//try visited each node and apply DFS if it's not visited
//after DFS (or BFS), all the nodes which are reachable will be marked as visited
//keep iterating to other nodes, if those are not visited, that must be a new connected component (another province)
for(int i=0; i<V; i++){
if(visited[i] == false){
dfs(i, adj, visited);
count++;
}
}
return count;
}
static void dfs(Integer node, ArrayList<ArrayList<Integer>> adj, boolean[] visited){
//if the node is already visited, return
if(visited[node]) return;
//else mark it as visited
visited[node] = true;
//check for neighbours
ArrayList<Integer> neighbours = adj.get(node);
//as per the question, if adj.get(node1).get(node2) == 1, then they are connected
for(int i=0; i<neighbours.size(); i++){
//if current node connectes to node i, call DFS for node i recursively
if(neighbours.get(i) == 1){
dfs(i, adj, visited);
}
}
}
};