Friend Circles

第34天。

今天的题目是Friend Circles:

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

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

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

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

vector<int> arr;
int root(vector<int> &arr, int i) {
    int root = i;
    while(arr[root] != -1) root = arr[root];
    return root;
}
void unionFunc(int i, int j) {
    i = root(arr, i); 
    j = root(arr, j);
    if (i == j) return;
    arr[j] = i;
}
int findCircleNum(vector<vector<int>>& M) {
    if (M.size() == 0) return 0;
    
    int size = M.size();
    arr = vector<int>(size, -1);
    
    for(int i = 0;i < size; i++) {
        for(int j = i+1;j < size; j++) {
            if (M[i][j]) {
                unionFunc(i, j);
            }   
        }
    }
    
    int res = 0;
    for(int i = 0;i < size; i++) res += (arr[i] == -1);
    return res;
}