题目描述

班上有N名学生。他们中的一些人是朋友，而有些则不是。他们的友谊本质上是传递性的。例如，如果A是B的直接朋友，而B是C的直接朋友，那么A是C的间接朋友。我们定义的朋友圈是一群直接或间接的朋友。

给定N * N矩阵M表示班级中学生之间的朋友关系。如果M [i] [j] = 1，那么第i和第j个学生是彼此的直接朋友，否则不是。而且你必须在所有学生中输出朋友圈的总数。

样例

输入：
[[1,1,0],
 [1,1,0],
 [0,0,1]]
输出：2
 学生0和学生1是直接朋友，所以他们俩是一个朋友圈，学生2跟自己是朋友，所以有两个朋友圈

算法1

(并查集) $O(n^2)$

并查集的基本题，发现两个人是朋友则将两个人的朋友圈进行合并，最后看有多少个集合（朋友圈）即可。

时间复杂度分析：需要遍历朋友圈矩阵，矩阵大小为$O(n^2)$，合并和查询操作平均复杂度为常数复杂度，因此最后复杂度为$O(n^2)$。

C++ 代码

class UnionFind{
public:
    vector<int>father;
    UnionFind(int num){//num表示元素的个数
        for(int i = 0; i < num; i++){
            father.push_back(i);//箭头指向自己
        }
    }
    int Find(int n){
        //递归
        if(father[n] == n)
            return n;
        father[n] = Find(father[n]);//路径压缩版本
        return father[n];
    }
    void Union(int a, int b){
        int fa = Find(a);
        int fb = Find(b);
        father[fb] = fa;
    }
};
class Solution {
public:  
    int findCircleNum(vector<vector<int>>& M) {
        int N = M.size();
        UnionFind UF(N);
        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                if(M[i][j]){
                    UF.Union(i, j);//两个人是朋友则合并朋友圈
                }
            }
        }
        int res = 0;
        for(int i = 0; i < N; i++){
            if(UF.Find(i) == i)//计算朋友圈的个数
                res++;
        }
        return res;
    }
};