Number of Provinces: Count Connected Components

114.5k
0

Given an N x N matrix isConnected, where isConnected[row][col] = 1 means city row and city col have a direct connection, return the total number of provinces.

A province is a group of cities connected directly or indirectly. The matrix is symmetric, and isConnected[city][city] = 1 for every city. Counting provinces is equivalent to counting connected components in an undirected graph represented by an adjacency matrix.

number of provinces

number of provinces

Example 1

Input: isConnected = [[1, 1, 0], [1, 1, 0], [0, 0, 1]]

Output: 2

Explanation: Cities 0 and 1 form one province. City 2 forms another province.

Example 2

Input: isConnected = [[1, 0, 0], [0, 1, 0], [0, 0, 1]]

Output: 3

Explanation: No direct connection exists between different cities, so every city forms a separate province.

Approach 1

Depth First Search explores every city reachable from a selected starting city before returning to examine another unvisited city. A complete DFS traversal covers one connected component, representing one province.

An outer loop examines every city, while a visited array prevents repeated processing. Every DFS call started from an unvisited city indicates the discovery of a new province.

Algorithm

  • Initialize a visited array of size N with all entries marked as unvisited. The array records whether a city has already been included in a discovered province.

  • Initialize provinceCount to 0. The variable stores the number of connected components found during traversal.

  • Traverse all cities using a loop. Encountering an unvisited city indicates the beginning of a new connected component, so increment provinceCount and start DFS from the city.

  • Mark the current city as visited inside DFS, preventing repeated processing through cyclic or bidirectional connections.

  • Scan the complete adjacency-matrix row of the current city. An entry equal to 1 represents a direct connection, so start a recursive DFS call for every directly connected unvisited city.

  • Return provinceCount after every city has been examined, as each DFS initiation represents exactly one province.

Dry Run

number-of-provinces-dfs-corrected

number-of-provinces-dfs-corrected

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
// Marks all cities that belong to the same province.
void dfs(int city, vector<vector<int>>& isConnected, vector<int>& visited) {
// Mark the current city as visited.
visited[city] = 1;
int n = isConnected.size();
// Check every city connected to the current city.
for (int nextCity = 0; nextCity < n; nextCity++) {
// If there is a connection and the city is not visited, visit it.
if (isConnected[city][nextCity] == 1 && visited[nextCity] == 0) {
dfs(nextCity, isConnected, visited);
}
}
}
public:
// Counts the total number of provinces using DFS.
int findCircleNum(vector<vector<int>>& isConnected) {
int n = isConnected.size();
vector<int> visited(n, 0);
int provinces = 0;
// Try to start DFS from every city.
for (int city = 0; city < n; city++) {
// A new unvisited city means a new province starts.
if (visited[city] == 0) {
provinces++;
// Visit all cities in this province.
dfs(city, isConnected, visited);
}
}
// Return the total province count.
return provinces;
}
};
// Driver code.
int main() {
vector<vector<int>> isConnected = {{1, 1, 0}, {1, 1, 0}, {0, 0, 1}};
Solution sol;
cout << sol.findCircleNum(isConnected);
return 0;
}

Complexity Analysis

Time Complexity: O(N×N), where N represents the total number of cities. Every city is visited once, and processing a city requires scanning all N entries in the corresponding adjacency-matrix row.

Space Complexity: O(N), where N represents the total number of cities. The visited array requires O(N) space, while the recursive DFS call stack can contain up to N cities in the worst case.

Approach 2

Breadth First Search uses a queue to explore all cities belonging to one province iteratively. Starting from an unvisited city, BFS processes every directly or indirectly connected city before the outer traversal continues.

The queue avoids recursive call-stack usage and processes connected cities level by level. Since connectivity is stored in an adjacency matrix, removing a city from the queue requires scanning the complete corresponding row to locate connected neighbors.

Algorithm

  • Initialize a visited array of size N with all entries marked as unvisited. The array prevents cities belonging to an already discovered province from starting another BFS traversal.

  • Initialize provinceCount to 0. The variable records the number of connected components discovered.

  • Traverse all cities using a loop. An unvisited city represents the starting point of a new province, so increment provinceCount and add the city to a queue.

  • Mark the starting city as visited before queue processing. Early marking prevents the same city from being inserted into the queue multiple times.

  • Continue processing until the queue becomes empty. For every removed city, scan the corresponding adjacency-matrix row to examine all possible connections.

  • Add every directly connected unvisited city to the queue and mark the city as visited. Queue insertion extends the current BFS traversal to all cities belonging to the same province.

  • Return provinceCount after all cities have been examined, as each BFS initiation corresponds to one complete province.

Dry Run

bfs

bfs

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Counts the total number of provinces using BFS.
int findCircleNum(vector<vector<int>>& isConnected) {
int n = isConnected.size();
vector<int> visited(n, 0);
int provinces = 0;
// Try to start BFS from every city.
for (int start = 0; start < n; start++) {
// Skip the city if it already belongs to a province.
if (visited[start] == 1) {
continue;
}
// A new unvisited city means a new province starts.
provinces++;
queue<int> q;
// Mark the starting city as visited.
visited[start] = 1;
// Push the starting city into the queue.
q.push(start);
// Process all cities in the current province.
while (!q.empty()) {
int city = q.front();
q.pop();
// Check every city connected to the current city.
for (int nextCity = 0; nextCity < n; nextCity++) {
// If connected and unvisited, add it to the same province.
if (isConnected[city][nextCity] == 1 && visited[nextCity] == 0) {
visited[nextCity] = 1;
q.push(nextCity);
}
}
}
}
// Return the total province count.
return provinces;
}
};
// Driver code.
int main() {
vector<vector<int>> isConnected = {{1, 0, 0}, {0, 1, 0}, {0, 0, 1}};
Solution sol;
cout << sol.findCircleNum(isConnected);
return 0;
}

Complexity Analysis

Time Complexity: O(N×N), where N represents the total number of cities. Every city enters and leaves the queue at most once, and processing a city requires scanning all N entries in the corresponding matrix row.

Space Complexity: O(N), where N represents the total number of cities. The visited array requires O(N) space, while the queue can store up to N cities in the worst case.

Approach 3

Disjoint Set Union initially treats every city as an independent province. The parent array stores the representative of each set, while the size array supports efficient merging by attaching the smaller set below the larger set.

A direct connection between two cities requires merging the corresponding sets. Every successful merge combines two previously separate provinces and reduces the province count by one. Since the adjacency matrix is symmetric, scanning only entries above the main diagonal avoids processing every undirected connection twice.

Algorithm

  • Initialize a DSU structure containing parent and size arrays of size N. Every city initially acts as a separate set representative with a set size of 1.

  • Initialize provinceCount to N, as N disconnected cities initially represent N separate provinces.

  • Traverse the upper triangle of the adjacency matrix. The outer loop selects a city i, while the inner loop examines cities j satisfying j > i, ensuring that every undirected city pair is checked only once.

  • Check whether matrix[i][j] equals 1. A value of 1 signifies a direct connection between cities i and j.

  • Find the ultimate representatives of cities i and j using path compression. Different representatives indicate two separate provinces.

  • Merge sets having different representatives using union by size. A successful merge combines two provinces, so decrement provinceCount.

  • Skip the merge when both cities already have the same representative, as both cities already belong to the same province.

  • Return provinceCount after all relevant city pairs have been processed, as the remaining DSU sets represent the final provinces.

Dry Run

number-of-provinces-dsu-easy

number-of-provinces-dsu-easy

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
// Finds the ultimate parent of a node.
int findParent(int node, vector<int>& parent) {
// Base case: the node is its own parent.
if (parent[node] == node) {
return node;
}
// Compress the path while finding the parent.
parent[node] = findParent(parent[node], parent);
// Return the ultimate parent.
return parent[node];
}
// Merges two city groups using union by size.
bool unite(int u, int v, vector<int>& parent, vector<int>& size) {
// Find the ultimate parent of both cities.
int pu = findParent(u, parent);
int pv = findParent(v, parent);
// If both cities already have the same parent, no merge is needed.
if (pu == pv) {
return false;
}
// Keep the larger group as the main parent.
if (size[pu] < size[pv]) {
swap(pu, pv);
}
// Attach the smaller group to the larger group.
parent[pv] = pu;
// Update the size of the merged group.
size[pu] += size[pv];
// Return true because a merge happened.
return true;
}
public:
// Counts the total number of provinces using DSU.
int findCircleNum(vector<vector<int>>& isConnected) {
int n = isConnected.size();
vector<int> parent(n);
vector<int> size(n, 1);
int provinces = n;
// Initially, every city is its own parent.
for (int city = 0; city < n; city++) {
parent[city] = city;
}
// Scan only the upper triangle because the matrix is symmetric.
for (int row = 0; row < n; row++) {
for (int col = row + 1; col < n; col++) {
// If two cities are connected and merged, one province reduces.
if (isConnected[row][col] == 1 && unite(row, col, parent, size)) {
provinces--;
}
}
}
// Return the remaining province count.
return provinces;
}
};
// Driver code.
int main() {
vector<vector<int>> isConnected = {{1, 1, 0}, {1, 1, 0}, {0, 0, 1}};
Solution sol;
cout << sol.findCircleNum(isConnected);
return 0;
}

Complexity Analysis

Time Complexity: O(N×N×α(N)), where N represents the total number of cities and α(N) represents the inverse Ackermann function. Upper-triangle traversal examines O(N×N) city pairs, and every connected pair can require optimized DSU operations. Each find or union operation takes O(α(N)) amortized time with path compression and union by size.

Space Complexity: O(N), where N represents the total number of cities. The DSU parent and size arrays each store one entry for every city, requiring O(N) auxiliary space.

Interview follow-up Questions

Yes. Province count equals connected component count in an undirected graph represented by an adjacency matrix.

Graph

Read Similar Blogs

Graph

Disjoint Set Union: Union by Rank, Size and Path Compression

Design a disjoint set, also called a union-find data structure, for N nodes numbered from 1 to N . Initially, every node belongs to a separate set. Support the following operations: D...

89.1k
Graph

Print Shortest Path

Given a weighted undirected graph with n vertices numbered from 1 to n and m edges, find a shortest path from vertex 1 to vertex n . Each edge appears as [u, v, weight] and every weight is positive...

96.1k
Graph

Network Delay Time Using Dijkstra's Algorithm

A network contains n nodes labeled from 1 to n . Each directed edge [u,v,w] means a signal needs w time units to travel from node u to node v . A signal starts from node k . Return the minimum time...

81.2k
Comments0