Practice › Graphs
Number of Provinces
Easy · Graphs · Asked at Amazon, Microsoft, Goldman Sachs, Bloomberg
M[i][j] = 1 means city i and city j are directly connected (the matrix is symmetric and M[i][i] = 1). A province is a group of cities connected directly or indirectly. Print the number of provinces.
Input
First line: n. Next n lines: n values (0 or 1).
Output
The number of provinces.
Constraints
- 1 ≤ n ≤ 200
Count how many times you start a new DFS/BFS from an unvisited city — or use union–find.
Example 1
Input
3 1 1 0 1 1 0 0 0 1
Output
2
Example 2
Input
3 1 0 0 0 1 0 0 0 1
Output
3
Hints
- The matrix is an adjacency matrix of an undirected graph.
- Count connected components: every time you find an unvisited city, start a DFS/BFS from it and add one.
Approach
Loop over cities; for each unvisited city, increment the answer and visit everything reachable from it (DFS with a stack, scanning the city's row of the matrix for neighbours). Union–find over all pairs with M[i][j] = 1 gives the same count.
Complexity: O(n²) time · O(n) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<vector<int>> M(n, vector<int>(n));
for (auto &row : M)
for (auto &x : row) cin >> x;
vector<bool> seen(n, false);
int count = 0;
for (int i = 0; i < n; i++) {
if (seen[i]) continue;
count++;
stack<int> st;
st.push(i);
seen[i] = true;
while (!st.empty()) {
int u = st.top();
st.pop();
for (int v = 0; v < n; v++)
if (M[u][v] && !seen[v]) seen[v] = true, st.push(v);
}
}
cout << count << "\n";
return 0;
}Python solution
import sys
data = list(map(int, sys.stdin.read().split()))
n = data[0]
M = [data[1 + i * n : 1 + (i + 1) * n] for i in range(n)]
seen, count = [False] * n, 0
for i in range(n):
if seen[i]:
continue
count += 1
seen[i] = True
stack = [i]
while stack:
u = stack.pop()
for v in range(n):
if M[u][v] and not seen[v]:
seen[v] = True
stack.append(v)
print(count)Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[][] M = new int[n][n];
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) M[i][j] = sc.nextInt();
boolean[] seen = new boolean[n];
int count = 0;
for (int i = 0; i < n; i++) {
if (seen[i]) continue;
count++;
Deque<Integer> st = new ArrayDeque<>();
st.push(i);
seen[i] = true;
while (!st.isEmpty()) {
int u = st.pop();
for (int v = 0; v < n; v++)
if (M[u][v] == 1 && !seen[v]) { seen[v] = true; st.push(v); }
}
}
System.out.println(count);
}
}