Code & Func

第34天。

一道图论的题目，求连通分量的个数。这道题之前考研复试面试时遇到过。

用并查集去做会比较快，但是需要对并查集做一定修改。

简单来说，并查集的数组全初始化为0，然后在遍历到M[i][j]==true时进行union操作.

遍历完后，arr中值为-1的元素的个数就是连通分量的个数：

1
vector<int> arr;
2
int root(vector<int> &arr, int i) {
3
    int root = i;
4
    while(arr[root] != -1) root = arr[root];
5
    return root;
6
}
7
void unionFunc(int i, int j) {
8
    i = root(arr, i);
9
    j = root(arr, j);
10
    if (i == j) return;
11
    arr[j] = i;
12
}
13
int findCircleNum(vector<vector<int>>& M) {
14
    if (M.size() == 0) return 0;
15

15 collapsed lines
16
    int size = M.size();
17
    arr = vector<int>(size, -1);
18

19
    for(int i = 0;i < size; i++) {
20
        for(int j = i+1;j < size; j++) {
21
            if (M[i][j]) {
22
                unionFunc(i, j);
23
            }
24
        }
25
    }
26

27
    int res = 0;
28
    for(int i = 0;i < size; i++) res += (arr[i] == -1);
29
    return res;
30
}