# 547. Number of Provinces

## Description

There are n cities. Some of them are connected, while some are not. If city a is connected directly with city b, and city b is connected directly with city c, then city a is connected indirectly with city c.

A province is a group of directly or indirectly connected cities and no other cities outside of the group.

You are given an n x n matrix isConnected where isConnected[i][j] = 1 if the ith city and the jth city are directly connected, and isConnected[i][j] = 0 otherwise.

Return the total number of provinces.

Example 1:

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


Example 2:

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


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]

## Solutions

• class Solution {
private int[][] g;
private boolean[] vis;

public int findCircleNum(int[][] isConnected) {
g = isConnected;
int n = g.length;
vis = new boolean[n];
int ans = 0;
for (int i = 0; i < n; ++i) {
if (!vis[i]) {
dfs(i);
++ans;
}
}
return ans;
}

private void dfs(int i) {
vis[i] = true;
for (int j = 0; j < g.length; ++j) {
if (!vis[j] && g[i][j] == 1) {
dfs(j);
}
}
}
}

• class Solution {
public:
int findCircleNum(vector<vector<int>>& isConnected) {
int n = isConnected.size();
int ans = 0;
bool vis[n];
memset(vis, false, sizeof(vis));
function<void(int)> dfs = [&](int i) {
vis[i] = true;
for (int j = 0; j < n; ++j) {
if (!vis[j] && isConnected[i][j]) {
dfs(j);
}
}
};
for (int i = 0; i < n; ++i) {
if (!vis[i]) {
dfs(i);
++ans;
}
}
return ans;
}
};

• class Solution:
def findCircleNum(self, isConnected: List[List[int]]) -> int:
def dfs(i: int):
vis[i] = True
for j, x in enumerate(isConnected[i]):
if not vis[j] and x:
dfs(j)

n = len(isConnected)
vis = [False] * n
ans = 0
for i in range(n):
if not vis[i]:
dfs(i)
ans += 1
return ans


• func findCircleNum(isConnected [][]int) (ans int) {
n := len(isConnected)
vis := make([]bool, n)
var dfs func(int)
dfs = func(i int) {
vis[i] = true
for j, x := range isConnected[i] {
if !vis[j] && x == 1 {
dfs(j)
}
}
}
for i, v := range vis {
if !v {
ans++
dfs(i)
}
}
return
}

• function findCircleNum(isConnected: number[][]): number {
const n = isConnected.length;
const vis: boolean[] = new Array(n).fill(false);
const dfs = (i: number) => {
vis[i] = true;
for (let j = 0; j < n; ++j) {
if (!vis[j] && isConnected[i][j]) {
dfs(j);
}
}
};
let ans = 0;
for (let i = 0; i < n; ++i) {
if (!vis[i]) {
dfs(i);
++ans;
}
}
return ans;
}


• impl Solution {
fn dfs(is_connected: &mut Vec<Vec<i32>>, vis: &mut Vec<bool>, i: usize) {
vis[i] = true;
for j in 0..is_connected.len() {
if vis[j] || is_connected[i][j] == 0 {
continue;
}
Self::dfs(is_connected, vis, j);
}
}

pub fn find_circle_num(mut is_connected: Vec<Vec<i32>>) -> i32 {
let n = is_connected.len();
let mut vis = vec![false; n];
let mut res = 0;
for i in 0..n {
if vis[i] {
continue;
}
res += 1;
Self::dfs(&mut is_connected, &mut vis, i);
}
res
}
}