并查集

题目是无向图，且给定n个点之间的关系，求得连通块的数量。

因为不涉及到权值，可以用并查集来做，最终查看下有多个集合即可。

1.初始化连通块数量为点的数量n

2.遍历邻接矩阵，如果两个点是相连的并且两个点不属于同一个集合，则将两个点合并，并且集合的数量-1。

时间复杂度$O(N^2$)，空间复杂度$O(N$)

AC代码

class Solution {
public:
    static const int N = 1e5 + 10;
    int p[N];

    int find(int x) {
        if (x != p[x]) return p[x] = find(p[x]);
        return p[x];
    }

    int findCircleNum(vector<vector<int>>& g) {
        int n = g.size();
        //初始化并查集
        for (int i = 0 ; i < n ; i ++) p[i] = i;
        int res = n;//默认所有点不相连，则有n个连通块
        for (int i = 0 ; i < n ; i ++) 
            for (int j = 0 ; j < n ; j ++) 
                //相连且不在一个连通块中
                if (g[i][j] == 1 && find(i) != find(j)) {
                    p[find(i)] = j;
                    res --;
        return res;

    }
};