Number of Provinces - Using Graph Traversal - Visualization

Graphs

Contents

VisualizationProblemExamplesSolutionAlgorithmCodeTimeSpace

Visualization Player

Problem Statement❯

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.

Examples❯

Graph Object Number of Provinces Description
{0: [1], 1: [0], 2: []}
2 Nodes 0 and 1 are connected, node 2 is isolated → 2 provinces.
{0: [], 1: [], 2: []}
3 Each node is isolated → 3 provinces.
{0: [1, 2], 1: [0, 2], 2: [0, 1]}
1 All nodes are connected → 1 province.
{0: []}
1 Only one node → 1 province.
{} 0 No nodes → 0 provinces.

Solution❯

YouTube Video - Detailed Understanding of Solution

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.

Algorithm Steps❯

  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.

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#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;
}

Time Complexity❯

CaseTime ComplexityExplanation
Best CaseO(V + E)If all nodes are part of one province, DFS/BFS will still touch all nodes and edges once.
Average CaseO(V + E)Each component is visited once, processing all its vertices and edges.
Worst CaseO(V + E)When all nodes are isolated, we perform V DFS/BFS calls with no edge visits.

Space Complexity❯

O(V)

Explanation: We maintain a visited set of size V.


Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...