Posts Number of Provinces
Post
Cancel

Number of Provinces

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.

geeksforgeeks

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);
            }
        }
        
    }
};
This post is licensed under CC BY 4.0 by the author.