547. Friend Circles

▶ 将一群人的关系网络划分为几个连通子图，且子图之间两两不连通，求这种连通子图的数量

● 代码，22 ms，深度优先遍历

 1 class Solution
 2 {
 3 public:
 4     void dfs(int root, vector<vector<int>>& M, vector<bool>& noVisited)
 5     {
 6         noVisited[root] = false;
 7         for (int i = 0; i < noVisited.size(); i++)
 8         {
 9             if (root != i && M[root][i] && noVisited[i])
10                 dfs(i, M, noVisited);
11         }
12     }
13     int findCircleNum(vector<vector<int>>& M)
14     {
15         const int n = M.size();
16         if (!n)
17             return 0;
18         int i, group;
19         vector<bool> noVisited(n, true);
20         for (i = group = 0; i < n; i++)
21             group += noVisited[i] ? (dfs(i, M, noVisited), 1) : 0;
22         return group;
23     }
24 };

● 代码，21 ms，建立森林，并且定义了专用于这类合并问题的类 UnionFind，本问题中可以完全去掉节点等级变量 rank

 1 class UnionFind
 2 {
 3 private:
 4     int cnt;
 5     vector<int> parent, rank;
 6 public:
 7     UnionFind(int n)
 8     {
 9         cnt = n;
10         parent = vector<int>(n, 0);
11         rank = vector<int>(n,0);
12         for (int i = 0; i < n; i++)
13             parent[i] = i;            
14     }
15     int find(int p)
16     {
17         for (; p != parent[p]; parent[p] = parent[parent[p]], p = parent[p]);                
18         return p;
19     }
20     void unionOperate(int p, int q)
21     {
22         int rootP = find(p), rootQ = find(q);// 找到 p 和 q 的源
23         if (rootP == rootQ)                  // 同源，相当于已经合并完成
24             return;
25         if (rank[rootQ] > rank[rootP])       // rootQ 的级数比较高，把 rootP 挂到 rootQ 上
26             parent[rootP] = rootQ;
27         else
28         {
29             parent[rootQ] = rootP;           // rootQ 挂到 rootP 上
30             if (rank[rootP] == rank[rootQ])  // 同层合并，把其中一个升一级
31                 rank[rootP]++;
32         }
33         cnt--;
34     }
35     int count() { return cnt; }
36 };
37 
38 class Solution
39 {
40 public:    
41     int findCircleNum(vector<vector<int>> M)
42     {
43         int n = M.size();
44         UnionFind uf(n);
45         for (int i = 0; i < n - 1; i++)
46         {
47             for (int j = i + 1; j < n; j++)
48                 if (M[i][j] == 1) uf.unionOperate(i, j);
49         }
50         return uf.count();
51     }
52 };

● 广度优先遍历，24 ms

 1 class Solution
 2 {
 3 public:
 4     int findCircleNum(vector<vector<int>>& M)
 5     {
 6         int i, count;
 7         for (i = count = 0; i < M.size(); i++)
 8             count += (M[i][i] == 1) ? (BFS(i, M), 1) : 0;
 9         return count;
10     }
11     void BFS(int root, vector<vector<int>>& M)
12     {
13         queue<int> qq;
14         int i, j, k;
15         for(qq.push(root);qq.size() > 0;)
16         {
17             for (i = 0; i < qq.size(); i++)
18             {
19                 j = qq.front(), qq.pop();                             
20                 for (M[j][j] = 2, k = 0; k < M[0].size(); k++)  // M[j][j] = 2 标记为已遍历
21                 {
22                     if (M[j][k] == 1 && M[k][k] == 1)
23                         qq.push(k);
24                 }
25             }
26         }
27     }
28 };

● 收录两个 python 的算法，分别为 201 ms 和 240 ms，已经是内置函数了

1 import scipy.sparse
2 class Solution(object) :
3     def findCircleNum(self, M) :
4         return scipy.sparse.csgraph.connected_components(M)[0]
5 
6 import numpy as np
7 class Solution(object) :
8     def findCircleNum(self, M) :
9         return len(set(map(tuple, (np.matrix(M, dtype = 'bool')**len(M)).A)))