Vultr DocsLatest Content

Number of Provinces

Updated on 27 June, 2025
Number of Provinces header image

Problem Statement

In this problem, we are working with a representation of cities and their connections. We represent n cities using an n x n matrix named isConnected. In this matrix, if isConnected[i][j] = 1, it means there is a direct connection between city i and city j. Conversely, isConnected[i][j] = 0 indicates no direct connection. This setup allows any city to be connected either directly or indirectly to other cities. A province is defined as a group of cities that are all directly or indirectly connected to one another, without links to any cities outside this group.

Your task is to determine the total number of such provinces. For every set of interconnected cities that form a self-contained network, it counts as one province.

Examples

Example 1

Input:

isConnected = [[1,1,0],[1,1,0],[0,0,1]]

Output:

2

Explanation:

Cities 0 and 1 are connected to each other.  
City 2 is isolated.  
So there are 2 provinces: [0,1] and [2].

Example 2

Input:

isConnected = [[1,0,0],[0,1,0],[0,0,1]]

Output:

3

Explanation:

Each city is isolated and forms its own province.  
So there are 3 provinces: [0], [1], and [2].

Constraints

  • 1 <= n <= 200
  • n == isConnected.length
  • n == isConnected[i].length
  • isConnected[i][j] is 1 or 0
  • isConnected[i][i] == 1
  • isConnected[i][j] == isConnected[j][i]

Approach and Intuition

Understanding how cities form provinces can be approached by visualizing this as a graph problem, where each city represents a node and each direct connection represents an edge.

To solve the problem, we can employ Depth-First Search (DFS), Breadth-First Search (BFS), or Union-Find. These techniques efficiently identify connected components (provinces) in a graph.

Steps to Approach:

  1. Initialize a counter for provinces.

  2. Use an auxiliary structure (like a boolean array) to track visited cities.

  3. Iterate through each city:

    • If the city has not been visited, it starts a new province.
    • Increment the province counter.
    • Launch a DFS or BFS from this city to visit all directly or indirectly connected cities, marking them as visited.

  4. At the end of the traversal, the counter reflects the total number of provinces.

DFS Approach

DFS works by exploring as far as possible along each branch before backtracking.

Union-Find Approach

Union-Find (Disjoint Set Union) groups cities into sets. Initially, each city is its own group. For every connection, cities are merged into the same group. The number of unique groups at the end equals the number of provinces.

Either approach works efficiently within the problem's constraints.

Solutions

  • C++
  • Java
  • Python
cpp 
class DisjointSet {
private:
    vector<int> lead, height;
    int componentCount;
    
public:
    DisjointSet(int elements) {
        lead.resize(elements);
        height.resize(elements, 0);
        componentCount = elements;
        for (int i = 0; i < elements; i++) {
            lead[i] = i;
        }
    }
    int findLeader(int x) {
        if (lead[x] != x) lead[x] = findLeader(lead[x]);
        return lead[x];
    }
    void connect(int x, int y) {
        int rootX = findLeader(x), rootY = findLeader(y);
        if (height[rootX] < height[rootY]) {
            lead[rootX] = rootY;
        } else if (height[rootX] > height[rootY]) {
            lead[rootY] = rootX;
        } else {
            lead[rootY] = rootX;
            height[rootX]++;
        }
    }
};
    
class Solution {
public:
    int findCircleNum(vector<vector<int>>& isConnected) {
        int cities = isConnected.size();
        DisjointSet ds(cities);
        int clusters = cities;
    
        for (int i = 0; i < cities; i++) {
            for (int j = i + 1; j < cities; j++) {
                if (isConnected[i][j] && ds.findLeader(i) != ds.findLeader(j)) {
                    clusters--;
                    ds.connect(i, j);
                }
            }
        }
    
        return clusters;
    }
};

In the provided C++ code, the problem of finding the number of provinces among cities connected by roads is addressed using a Disjoint Set (Union-Find) data structure. The main objectives are to determine if two cities are directly or indirectly connected, and to compute groups of connected cities, which are termed as provinces.

The code includes two main components:

  • DisjointSet Class: This class is specially designed to keep track of the elements that are leaders of their set and to perform efficient unions of sets.

    • Key Methods in DisjointSet:

      • DisjointSet(int elements): Initializes a set for each element where each element is its own leader and the height (for union by rank) is set to zero.
      • findLeader(int x): Retrieves the root leader of the set to which element x belongs, using path compression for optimization.
      • connect(int x, int y): Connects the sets of x and y. If x and y have different root leaders, the trees are unioned by height to maintain balanced tree structures.

  • Solution Class: This class uses an instance of DisjointSet to solve the problem by determining the number of connected components (provinces).

    • Method in Solution:

      • findCircleNum(vector<vector<int>>& isConnected): Examines a matrix where isConnected[i][j] indicates if city i is directly connected to city j. The method checks all pairs of cities, and if they are connected but belong to different sets, a union operation is performed. After processing all city connections, the number of disjoint sets (provinces) is calculated by counting how many unique leaders exist.

The algorithm initiates with treating each city as its own province. As connections are discovered (direct or indirect), the number of provinces decreases through the union operations, counting the remaining distinct sets using the clusters variable.

This setup efficiently determines groups of interconnected cities, representing how many separate connected groupings (provinces) are present, ensuring optimal complexity and performance using the Disjoint Set structure.

java 
class DisjointSet {
    
    int[] leader;
    int[] size;
    
    public DisjointSet(int length) {
        leader = new int[length];
        for (int i = 0; i < length; i++) leader[i] = i;
        size = new int[length];
    }
    
    public int find(int p) {
        if (leader[p] != p) leader[p] = find(leader[p]);
        return leader[p];
    }
    
    public void link(int p, int q) {
        int rootP = find(p), rootQ = find(q);
        if (rootP == rootQ) {
            return;
        } else if (size[rootP] < size[rootQ]) {
            leader[rootP] = rootQ;
        } else if (size[rootP] > size[rootQ]) {
            leader[rootQ] = rootP;
        } else {
            leader[rootQ] = rootP;
            size[rootP]++;
        }
    }
}
    
class Solution {
    
    public int findCircleNum(int[][] isConnected) {
        int numProvinces = isConnected.length;
        DisjointSet ds = new DisjointSet(numProvinces);
        int componentsCount = numProvinces;
    
        for (int i = 0; i < numProvinces; i++) {
            for (int j = i + 1; j < numProvinces; j++) {
                if (isConnected[i][j] == 1 && ds.find(i) != ds.find(j)) {
                    componentsCount--;
                    ds.link(i, j);
                }
            }
        }
    
        return componentsCount;
    }
}

This summary explains the Java solution to the problem of finding the number of provinces represented as a graph of connected cities. The code uses the Disjoint Set (Union-Find) data structure to dynamically manage the grouping of individual cities into provinces based on a connectivity matrix.

  • The DisjointSet class initializes with each city as its own leader, indicating it forms a separate province initially. Methods include find, which returns the representative leader of a city using path compression to flatten the structure, and link that unites two sets based on their size to keep the data structure optimally flat.

  • The Solution class method findCircleNum calculates the number of provinces by iterating through the upper half of the symmetric connectivity matrix. Connected cities are unioned in the disjoint set, reducing the component count each time cities from different sets are connected.

  • Each time two cities are found to be connected (isConnected[i][j] == 1), check if they belong to the same province already using find. If they don't, link them using link, effectively merging the components they belong to.

This implementation effectively counts the distinct provinces by managing union operations efficiently through the union-by-size and path compression strategies of the disjoint set.

python 
class DisjointSet:
    def __init__(self, size):
        self.root = list(range(size))
        self.tree_height = [0] * size
    
    def root_find(self, x):
        if self.root[x] != x:
            self.root[x] = self.root_find(self.root[x])
        return self.root[x]
    
    def merge(self, x, y):
        root_x = self.root_find(x)
        root_y = self.root_find(y)
        if self.tree_height[root_x] < self.tree_height[root_y]:
            self.root[root_x] = root_y
        elif self.tree_height[root_x] > self.tree_height[root_y]:
            self.root[root_y] = root_x
        else:
            self.root[root_y] = root_x
            self.tree_height[root_x] += 1
    
    
class ProvinceCounter:
    def countProvinces(self, isConnected):
        count_nodes = len(isConnected)
        ds = DisjointSet(count_nodes)
        province_count = count_nodes
    
        for i in range(count_nodes):
            for j in range(i + 1, count_nodes):
                if isConnected[i][j] == 1 and ds.root_find(i) != ds.root_find(j):
                    province_count -= 1
                    ds.merge(i, j)
    
        return province_count

The provided Python code implements a solution to the problem of determining the number of provinces, where each province is represented as a connected component in an undirected graph. The solution uses a disjoint set (or union-find) data structure.

  • Python classes DisjointSet and ProvinceCounter are defined.
  • The DisjointSet class manages the union-find operations with methods to find the root of an element (root_find) and to union two subsets (merge).
  • The ProvinceCounter class includes a method countProvinces that calculates the number of provinces based on the isConnected matrix:
    • Each element i, j in the matrix indicates whether node i is directly connected to node j.
    • An instance of DisjointSet is initialized with the number of nodes.
    • The countProvinces method iterates over each element in the matrix, performing a merge operation for directly connected nodes and decrementing the province count for each successful union.
    • The method finally returns the total number of distinct provinces, which correspond to the number of connected components in the graph.

This solution efficiently groups and counts connected components in the graph using union-find, which is optimal for such problems that require determining connectedness and component counts in a graph-based structure.

Comments

No comments yet.