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 <= 200n == isConnected.lengthn == isConnected[i].lengthisConnected[i][j] is 1 or 0.isConnected[i][i] == 1isConnected[i][j] == isConnected[j][i]
Solutions#
Solution 1#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| 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
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| 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);
}
}
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| 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;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| 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
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| 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;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| 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
}
}
|
Solution 2#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution:
def findCircleNum(self, isConnected: List[List[int]]) -> int:
def find(x: int) -> int:
if p[x] != x:
p[x] = find(p[x])
return p[x]
n = len(isConnected)
p = list(range(n))
ans = n
for i in range(n):
for j in range(i + 1, n):
if isConnected[i][j]:
pa, pb = find(i), find(j)
if pa != pb:
p[pa] = pb
ans -= 1
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| class Solution {
private int[] p;
public int findCircleNum(int[][] isConnected) {
int n = isConnected.length;
p = new int[n];
for (int i = 0; i < n; ++i) {
p[i] = i;
}
int ans = n;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if (isConnected[i][j] == 1) {
int pa = find(i), pb = find(j);
if (pa != pb) {
p[pa] = pb;
--ans;
}
}
}
}
return ans;
}
private int find(int x) {
if (p[x] != x) {
p[x] = find(p[x]);
}
return p[x];
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| class Solution {
public:
int findCircleNum(vector<vector<int>>& isConnected) {
int n = isConnected.size();
int p[n];
iota(p, p + n, 0);
function<int(int)> find = [&](int x) -> int {
if (p[x] != x) {
p[x] = find(p[x]);
}
return p[x];
};
int ans = n;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if (isConnected[i][j]) {
int pa = find(i), pb = find(j);
if (pa != pb) {
p[pa] = pb;
--ans;
}
}
}
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| func findCircleNum(isConnected [][]int) (ans int) {
n := len(isConnected)
p := make([]int, n)
for i := range p {
p[i] = i
}
var find func(x int) int
find = func(x int) int {
if p[x] != x {
p[x] = find(p[x])
}
return p[x]
}
ans = n
for i := 0; i < n; i++ {
for j := 0; j < n; j++ {
if isConnected[i][j] == 1 {
pa, pb := find(i), find(j)
if pa != pb {
p[pa] = pb
ans--
}
}
}
}
return
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| function findCircleNum(isConnected: number[][]): number {
const n = isConnected.length;
const p: number[] = new Array(n);
for (let i = 0; i < n; ++i) {
p[i] = i;
}
const find = (x: number): number => {
if (p[x] !== x) {
p[x] = find(p[x]);
}
return p[x];
};
let ans = n;
for (let i = 0; i < n; ++i) {
for (let j = i + 1; j < n; ++j) {
if (isConnected[i][j]) {
const pa = find(i);
const pb = find(j);
if (pa !== pb) {
p[pa] = pb;
--ans;
}
}
}
}
return ans;
}
|
