05 August 2008
There are N students in a class. Some of them are friends, while some are not. Their friendship is transitive in nature. For example, if A is a direct friend of B, and B is a direct friend of C, then A is an indirect friend of C. And we defined a friend circle is a group of students who are direct or indirect friends.
Given a N*N matrix M representing the friend relationship between students in the class. If M[i][j] = 1, then the ith and jth students are direct friends with each other, otherwise not. And you have to output the total number of friend circles among all the students.
Example 1:
1
2
3
4
5
6
7
Input:
[[1,1,0],
[1,1,0],
[0,0,1]]
Output: 2
Explanation:The 0th and 1st students are direct friends, so they are in a friend circle.
The 2nd student himself is in a friend circle. So return 2.
Example 2:
1
2
3
4
5
6
7
Input:
[[1,1,0],
[1,1,1],
[0,1,1]]
Output: 1
Explanation:The 0th and 1st students are direct friends, the 1st and 2nd students are direct friends,
so the 0th and 2nd students are indirect friends. All of them are in the same friend circle, so return 1.
Note:
求朋友圈的个数，题目中对于朋友圈的定义是transitive的，比如A和B是好友，B和C是好友，那么即使A和C不是好友，那么他们三人也属于一个朋友圈。
1）DFS， 对于某个人，遍历其好友，然后再遍历其好友的好友，那么就能把属于同一个朋友圈的人都遍历一遍，同时标记出已经遍历过的人，然后累积朋友圈的个数，再去对于没有遍历到的人在找其朋友圈的人，这样就能求出个数。
2）BFS，思路同DFS，较慢。
3）Union Find，这道题是并查集的典型实现，跟323 Number of Connected Components in an Undirected Graph 和 261 Graph Valid Tree 解法类似； 初始时给每一个对象都赋上不同的标签，然后对于属于同一类的对象，在root中查找其标签，如果不同，那么将其中一个对象的标签赋值给另一个对象，注意root数组中的数字跟数字的坐标是有很大关系的，root存的是属于同一组的另一个对象的坐标，这样通过getRoot函数可以使同一个组的对象返回相同的值。
DFS
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 {
public int findCircleNum(int[][] M) {
int result = 0;
if (M == null || M.length == 0 || M[0].length == 0) {
return result;
}
int[] visited = new int[M.length];
for (int i = 0; i < M.length; i++) {// 按照行来检查，每一行是一个人
if (visited[i] == 0) { // visited对应的为0，表示未在之前的DFS中未被访问到，自己形成一个新圈子
dfs(M, visited, i);
result++;
}
}
return result;
}
private void dfs(int[][] M, int[] visited, int i) {
for (int j = 0; j < M[i].length; j++) { // 将当前人物M[i]的朋友通过dfs找出来，并标记
if (M[i][j] == 1 && visited[j] == 0) {// 是朋友，且没有被访问过
visited[j] = 1;
dfs(M, visited, j); // 再根据朋友的朋友继续深搜
}
}
}
}
BFS
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
class Solution {
public int findCircleNum(int[][] M) {
int result = 0;
if (M == null || M.length == 0 || M[0].length == 0) {
return result;
}
for (int i = 0; i < M.length; i++) { // 依然按行检查
if (M[i][i] == 1) { // BFS的过程中尚未被加入到之前的圈子中，这时候”自成一圈“
bfs(M, i);
result++;
}
}
return result;
}
private void bfs(int[][] M, int oneGuy) {
Queue<Integer> queue = new LinkedList<>();
queue.offer(oneGuy);
while (!queue.isEmpty()) {
int size = queue.size(); //当前的bfs圈
for (int i = 0; i < size; i++) {
int anotherGuy = queue.poll();
M[anotherGuy][anotherGuy] = 2; // 先把找出来的在当前朋友圈中的人标记一下
// 把找出来的人的朋友加入到队列中，以后分析
for (int x = 0; x < M[anotherGuy].length; x++) {
if (M[anotherGuy][x] == 1 && M[x][x] != 2) { //是朋友，并且没有被标记过
queue.offer(x);
}
}
}
}
}
}
Union Find
单独的类
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
43
44
45
46
47
48
49
50
51
52
53
class Solution {
public int findCircleNum(int[][] M) {
if (M == null || M.length == 0 || M[0].length == 0) {
return 0;
}
int len = M.length;
UnionFind uf = new UnionFind(len);
for (int i = 0; i < len; i++) {
for (int j = 0; j <= i; j++) {
if (i == j) {
continue;
}
if (M[i][j] == 1) {
uf.union(i, j);
}
}
}
int[] father = uf.father;
int count = 0;
for (int i = 0; i < len; i++) {
if (father[i] == i) { // 查找有多少个老大，如果自己到顶点了，自增1
count++;
}
}
return count;
}
// 并查集模板
class UnionFind {
private int[] father = null;
public UnionFind(int n) {
father = new int[n];
for(int i = 0; i < n; ++i) {
father[i] = i;
}
}
public int find(int x) {
// 路径压缩
return father[x] == x ? x : ( father[x] = find(father[x]) );
}
public void union(int a,int b) {
int root_a = find(a);
int root_b = find(b);
if(root_a != root_b) {
father[root_a] = root_b;
}
}
}
}
内部方法
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
43
44
45
46
47
48
49
class Solution {
public int findCircleNum(int[][] M) {
int len = M.length;
if (len == 0) {
return 0;
}
// init，初始各人是各人的朋友圈
int[] parent = new int[len];
for (int k = 0; k < len; k++) {
parent[k] = k;
}
int result = len; // 初始每个人是一个朋友圈，共len个
for (int i = 0; i < len; i++) { // 遍历每一个人
for (int j = i + 1; j < len; j++) { // 只检查当前i的斜线右边的横排
if (M[i][j] == 0) { // i和j不是朋友
continue;
}
if (find(i, parent) == find(j, parent)) { // 已经在一个朋友圈
continue;
}
union(i, j, parent); // M[i][j] == 1，是朋友
result--; // 能union一个，减少一个最初为len的朋友圈
}
}
return result;
}
// 以下为Union Find的路径压缩代码
private int find(int p, int[] parent) {
if (parent[p] == p) {
return p;
}
parent[p] = find(parent[p], parent); // UF的路径压缩
return parent[p];
}
private void union(int p1, int p2, int[] parent) {
int f1 = find(p1, parent);
int f2 = find(p2, parent);
if (f1 != f2) {
parent[f1] = f2;
}
}
}