【并查集】 【DFS】
班上有 N 名学生。其中有些人是朋友，有些则不是。他们的友谊具有是传递性。如果已知 A 是 B 的朋友，B 是 C 的朋友，那么我们可以认为 A 也是 C 的朋友。所谓的朋友圈，是指所有朋友的集合。
给定一个 N * N 的矩阵 M，表示班级中学生之间的朋友关系。如果M[i][j] = 1，表示已知第 i 个和 j 个学生互为朋友关系，否则为不知道。你必须输出所有学生中的已知的朋友圈总数。
示例 1:
输入:
[[1,1,0],
[1,1,0],
[0,0,1]]
输出: 2
说明：已知学生0和学生1互为朋友，他们在一个朋友圈。
第2个学生自己在一个朋友圈。所以返回2。
示例 2:
输入:
[[1,1,0],
[1,1,1],
[0,1,1]]
输出: 1
说明：已知学生0和学生1互为朋友，学生1和学生2互为朋友，所以学生0和学生2也是朋友，所以他们三个在一个朋友圈，返回1。
注意：
N 在[1,200]的范围内。
对于所有学生，有$M[i][i]$ = 1。
如果有$M[i][j]$ = 1，则有$M[j][i]$ = 1。
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
32
33
34
35
36
37
38
39
40
41
42
class Solution {
private int [] stu ;
private int unions = 0 ;
public int findCircleNum ( int [][] M ) {
int number = M . length ;
stu = new int [ number ];
/* initialize */
for ( int i = 0 ; i < number ; i ++) {
stu [ i ] = i ;
}
for ( int i = 0 ; i < number ; i ++) {
for ( int j = i + 1 ; j < number ; j ++) { /* 如果有M[i][j] = 1，则有M[j][i] = 1。 */
if ( M [ i ][ j ] == 1 ) {
union ( i , j );
}
}
}
return number - unions ;
}
private int root ( int i ) {
while ( true ) {
if ( i == stu [ i ]) {
return i ;
}
stu [ i ] = stu [ stu [ i ]]; /* path improvement */
i = stu [ i ];
}
}
private void union ( int p , int q ) {
int i = root ( p );
int j = root ( q );
if ( i == j ) {
return ;
}
stu [ i ] = j ;
unions ++;
}
}
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
class Solution {
private int n ;
public int findCircleNum ( int [][] M ) {
n = M . length ;
int circleNum = 0 ;
boolean [] hasVisited = new boolean [ n ];
for ( int i = 0 ; i < n ; i ++) {
if (! hasVisited [ i ]) {
dfs ( M , i , hasVisited );
circleNum ++;
}
}
return circleNum ;
}
private void dfs ( int [][] M , int i , boolean [] hasVisited ) {
hasVisited [ i ] = true ;
for ( int k = 0 ; k < n ; k ++) {
if ( M [ i ][ k ] == 1 && ! hasVisited [ k ]) {
dfs ( M , k , hasVisited );
}
}
}
}