Code & Fun

第34天。

今天的题目是Friend Circles:

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

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

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

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

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
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;
}

本文首发于Code & Fun