Number of Provinces in an Undirected Graph

Problem Statement: You are given an undirected graph with V vertices, represented as an adjacency list. Two nodes u and v belong to the same province if there is a path from u to v or vice versa. Your task is to determine how many such provinces (connected components) exist in the graph.

Understanding the Problem

We are given an undirected graph where each node represents a city, and edges represent direct connections between them. A province is a group of cities that are all connected directly or indirectly. In graph terms, this means we are looking for the number of connected components.

Our goal is to count how many such groups (or provinces) exist in the graph. We’ll do this using a graph traversal algorithm like DFS (Depth-First Search).

How We Solve It – Step by Step

1. Start with an empty visited set to keep track of nodes we've already explored.
2. Initialize provinceCount = 0.
3. Loop through every node in the graph:
   1. If the node is not visited, it's the start of a new province.
   2. We perform DFS from that node to visit all connected nodes.
   3. After the DFS finishes, we increment provinceCount.
4. Once all nodes are processed, provinceCount gives us the number of provinces.

Working Example

Graph Input: {1: [3], 2: [4, 5], 3: [1], 4: [2], 5: [2]}

This graph has two separate clusters of cities:

• Province 1: Nodes 1 and 3 are connected.
• Province 2: Nodes 2, 4, and 5 are connected.

Step-by-Step Traversal

• Start with an empty visited set.
• Start DFS from node 1:
  • Mark 1 as visited
  • Visit neighbor 3 → mark 3

  → Province 1 found

• Next unvisited node: 2
  • Mark 2 as visited
  • Visit 4 → mark 4
  • Visit 5 → mark 5

  → Province 2 found

• Remaining nodes (3, 4, 5) are already visited, so we skip them

Total provinces = 2

Incorporating Edge Cases

Case 1: Empty Graph

• Input: {}
• Explanation: No nodes exist → no provinces
• Answer: 0

Case 2: All Nodes Are Isolated

• Input: {1: [], 2: [], 3: []}
• Explanation: Each node is its own province
• Answer: 3

Case 3: Fully Connected Graph

• Input: {1: [2, 3], 2: [1, 3], 3: [1, 2]}
• Explanation: All nodes reachable → one big province
• Answer: 1

Case 4: Multiple Groups

• Input: {0: [1], 1: [0], 2: [], 3: [4], 4: [3]}
• Explanation: (0,1), (3,4), and 2 form three separate groups
• Answer: 3

Conclusion

Using DFS (or BFS), we can efficiently find all connected cities starting from each unvisited node and count how many such groups exist. That gives us the total number of provinces in the graph.

1. Initialize a visited set to keep track of nodes we've already explored.
2. Initialize provinceCount = 0.
3. Loop through each node i in the graph:
1. If i is not in visited:
1. Perform DFS or BFS from node i.
2. During traversal, mark all reachable nodes as visited.
3. Increment provinceCount.
4. Return provinceCount.

Watch the accompanying explanation

#include <stdio.h>
#define N 3

void dfs(int graph[N][N], int visited[N], int node) {
    visited[node] = 1;
    for (int i = 0; i < N; i++) {
        if (graph[node][i] && !visited[i]) {
            dfs(graph, visited, i);
        }
    }
}

int findProvinces(int graph[N][N]) {
    int visited[N] = {0};
    int provinces = 0;
    for (int i = 0; i < N; i++) {
        if (!visited[i]) {
            dfs(graph, visited, i);
            provinces++;
        }
    }
    return provinces;
}

int main() {
    int graph[N][N] = {
        {1, 1, 0},
        {1, 1, 0},
        {0, 0, 1}
    };
    printf("Provinces: %d\n", findProvinces(graph));
    return 0;
}

#include <iostream>
#include <vector>
using namespace std;

void dfs(vector<vector<int>>& graph, vector<bool>& visited, int node) {
    visited[node] = true;
    for (int i = 0; i < graph[node].size(); i++) {
        if (graph[node][i] == 1 && !visited[i]) {
            dfs(graph, visited, i);
        }
    }
}

int findProvinces(vector<vector<int>>& graph) {
    int n = graph.size();
    vector<bool> visited(n, false);
    int provinces = 0;
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            dfs(graph, visited, i);
            provinces++;
        }
    }
    return provinces;
}

int main() {
    vector<vector<int>> graph = {
        {1, 1, 0},
        {1, 1, 0},
        {0, 0, 1}
    };
    cout << "Provinces: " << findProvinces(graph) << endl;
    return 0;
}

def dfs(graph, visited, node):
    visited[node] = True
    for neighbor in range(len(graph)):
        if graph[node][neighbor] == 1 and not visited[neighbor]:
            dfs(graph, visited, neighbor)

def find_provinces(graph):
    n = len(graph)
    visited = [False] * n
    provinces = 0
    for i in range(n):
        if not visited[i]:
            dfs(graph, visited, i)
            provinces += 1
    return provinces

matrix = [
    [1, 1, 0],
    [1, 1, 0],
    [0, 0, 1]
]
print("Provinces:", find_provinces(matrix))

public class Provinces {
    static void dfs(int[][] graph, boolean[] visited, int node) {
        visited[node] = true;
        for (int i = 0; i < graph.length; i++) {
            if (graph[node][i] == 1 && !visited[i]) {
                dfs(graph, visited, i);
            }
        }
    }

    static int findProvinces(int[][] graph) {
        int n = graph.length;
        boolean[] visited = new boolean[n];
        int provinces = 0;
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                dfs(graph, visited, i);
                provinces++;
            }
        }
        return provinces;
    }

    public static void main(String[] args) {
        int[][] graph = {
            {1, 1, 0},
            {1, 1, 0},
            {0, 0, 1}
        };
        System.out.println("Provinces: " + findProvinces(graph));
    }
}

function findCircleNum(graph) {
  const visited = new Set();
  let provinces = 0;

  function dfs(node) {
    for (const neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        dfs(neighbor);
      }
    }
  }

  for (const node in graph) {
    const nodeNum = Number(node);
    if (!visited.has(nodeNum)) {
      visited.add(nodeNum);
      dfs(nodeNum);
      provinces++;
    }
  }

  return provinces;
}

console.log("Provinces:", findCircleNum({0: [1], 1: [0], 2: []}));

package main

import (
    "fmt"
)

func dfs(graph [][]int, visited []bool, node int) {
    visited[node] = true
    for i := 0; i < len(graph); i++ {
        if graph[node][i] == 1 && !visited[i] {
            dfs(graph, visited, i)
        }
    }
}

func findProvinces(graph [][]int) int {
    n := len(graph)
    visited := make([]bool, n)
    provinces := 0
    for i := 0; i < n; i++ {
        if !visited[i] {
            dfs(graph, visited, i)
            provinces++
        }
    }
    return provinces
}

func main() {
    graph := [][]int{
        {1, 1, 0},
        {1, 1, 0},
        {0, 0, 1},
    }
    fmt.Println("Provinces:", findProvinces(graph))
}

fn dfs(graph: &Vec<Vec<i32>>, visited: &mut Vec<bool>, node: usize) {
    visited[node] = true;
    for (i, &val) in graph[node].iter().enumerate() {
        if val == 1 && !visited[i] {
            dfs(graph, visited, i);
        }
    }
}

fn find_provinces(graph: Vec<Vec<i32>>) -> i32 {
    let n = graph.len();
    let mut visited = vec![false; n];
    let mut provinces = 0;
    for i in 0..n {
        if !visited[i] {
            dfs(&graph, &mut visited, i);
            provinces += 1;
        }
    }
    provinces
}

fn main() {
    let graph = vec![
        vec![1, 1, 0],
        vec![1, 1, 0],
        vec![0, 0, 1],
    ];
    println!("Provinces: {}", find_provinces(graph));
}

fun dfs(graph: Array<IntArray>, visited: BooleanArray, node: Int) {
    visited[node] = true
    for (i in graph.indices) {
        if (graph[node][i] == 1 && !visited[i]) {
            dfs(graph, visited, i)
        }
    }
}

fun findProvinces(graph: Array<IntArray>): Int {
    val n = graph.size
    val visited = BooleanArray(n)
    var provinces = 0
    for (i in 0 until n) {
        if (!visited[i]) {
            dfs(graph, visited, i)
            provinces++
        }
    }
    return provinces
}

fun main() {
    val graph = arrayOf(
        intArrayOf(1, 1, 0),
        intArrayOf(1, 1, 0),
        intArrayOf(0, 0, 1)
    )
    println("Provinces: ${findProvinces(graph)}")
}

func dfs(_ graph: [[Int]], _ visited: inout [Bool], _ node: Int) {
    visited[node] = true
    for i in 0..<graph.count {
        if graph[node][i] == 1 && !visited[i] {
            dfs(graph, &visited, i)
        }
    }
}

func findProvinces(_ graph: [[Int]]) -> Int {
    let n = graph.count
    var visited = [Bool](repeating: false, count: n)
    var provinces = 0
    for i in 0..<n {
        if !visited[i] {
            dfs(graph, &visited, i)
            provinces += 1
        }
    }
    return provinces
}

let graph = [
    [1, 1, 0],
    [1, 1, 0],
    [0, 0, 1]
]
print("Provinces: \(findProvinces(graph))")

function dfs(graph: number[][], visited: boolean[], node: number): void {
  visited[node] = true;
  for (let i = 0; i < graph.length; i++) {
    if (graph[node][i] === 1 && !visited[i]) {
      dfs(graph, visited, i);
    }
  }
}

function findProvinces(graph: number[][]): number {
  const n = graph.length;
  const visited = new Array(n).fill(false);
  let provinces = 0;
  for (let i = 0; i < n; i++) {
    if (!visited[i]) {
      dfs(graph, visited, i);
      provinces++;
    }
  }
  return provinces;
}

const graph = [
  [1, 1, 0],
  [1, 1, 0],
  [0, 0, 1]
];

console.log("Provinces:", findProvinces(graph));

Time complexity

Space complexity

O(V)

We maintain a visited set of size V.