Depth-First Search
Breadth-First Search
Union Find
Graph
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
Solution 1
Python3 Java C++ Go TypeScript Rust
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
Python3 Java C++ Go TypeScript
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 ;
}
GitHub