infrastructureDataStructure6

发表于 分类于 ，

题目描述[原题链接][https://leetcode-cn.com/problems/friend-circles/]

班上有 N 名学生。其中有些人是朋友，有些则不是。他们的友谊具有是传递性。如果已知 A 是 B 的朋友，B 是 C 的朋友，那么我们可以认为 A 也是 C 的朋友。所谓的朋友圈，是指所有朋友的集合。

给定一个 N * N 的矩阵 M，表示班级中学生之间的朋友关系。如果M[i][j] = 1，表示已知第 i 个和 j 个学生互为朋友关系，否则为不知道。你必须输出所有学生中的已知的朋友圈总数。

示例 1:

1
2
3
4
5
6
7
输入: 
[[1,1,0],
 [1,1,0],
 [0,0,1]]
输出: 2 
说明：已知学生0和学生1互为朋友，他们在一个朋友圈。
第2个学生自己在一个朋友圈。所以返回2。

示例 2:

1
2
3
4
5
6
输入: 
[[1,1,0],
 [1,1,1],
 [0,1,1]]
输出: 1
说明：已知学生0和学生1互为朋友，学生1和学生2互为朋友，所以学生0和学生2也是朋友，所以他们三个在一个朋友圈，返回1。

注意：

  1. N 在[1,200]的范围内。
  2. 对于所有学生，有M[i][i] = 1。
  3. 如果有M[i][j] = 1，则有M[j][i] = 1。

算法描述

这题典型的并查集的题，并查集包括三个函数，一个是fin(int x)找到父节点的值，第二个函数meg(int x,int y)连接函数，将相联系的节点联系起来，第三个函数same(int x,int y)判断函数，判断两个点是否是同一个父节点;遍历完二维数组后，遍历father数组，当father[i]==i的时候就代表一个朋友圈，最后统计出有多少朋友圈即可；

C++代码

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
class Solution {
public:
    vector<int> father;
    int fin(int x){
      return father[x]=father[x]==x?x:fin(father[x]);
    }
  
    void meg(int x,int y){
      int a = fin(x),b=fin(y);
      father[a]=b;
    }
  
    bool same(int x,int y){
      return fin(x)==fin(y);
    }
  
    int findCircleNum(vector<vector<int>>& M) {
        father = vector<int>(M.size(),0);
        for(int i=0;i<M.size();i++){
          father[i]=i;
        }
        for(int i=0;i<M.size();i++){
          for(int j=0;j<i+1;j++){
            if(M[i][j]){
              if(!same(i,j)){
                meg(i,j);
              }
            }
          }
        }
      int ans=0;
      for(int i=0;i<father.size();i++)
      {
        if(father[i]==i){
          ans++;
        }
      }
      return ans;
    }
};

Java代码

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
class Solution {
    int[] father;
    int fin(int x){
        return father[x] = father[x]==x?x:fin(father[x]);
    }

    void meg(int x,int y){
        int a = fin(x),b=fin(y);
        father[a]=b;
    }

    boolean same(int x,int y){
        return fin(x)==fin(y);
    }

    public int findCircleNum(int[][] M) {
        father = new int[M.length];
        for(int i=0;i<M.length;i++){
            father[i]=i;
        }
        for(int i=0;i<M.length;i++){
            for(int j=0;j<i+1;j++){
                if(M[i][j]==1){
                    if(!same(i,j))
                        meg(i,j);
                }
            }
        }
        int ans = 0;
        for(int i=0;i<father.length;i++){
            if(i==father[i])
                ans++;
        }
        return ans;
    }
}