Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. The matrix is an adjacency matrix of an undirected graph.
  2. 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);
    }
}

Solve Number of Provinces online · All practice problems