LeetCode-547. 朋友圈
难度:中等
问题描述 班上有 N 名学生。其中有些人是朋友,有些则不是。他们的友谊具有是传递性。如果已知 A 是 B 的朋友,B 是 C 的朋友,那么我们可以认为 A 也是 C 的朋友。所谓的朋友圈,是指所有朋友的集合。
给定一个 N * N 的矩阵 M ,表示班级中学生之间的朋友关系。如果M[i][j] = 1,表示已知第 i 个和 j 个学生 互为 朋友关系,否则为不知道。你必须输出所有学生中的已知的朋友圈总数。
样例输入输出 示例1:
1 2 3 4 5 6 7 输入: [[1,1,0], [1,1,0], [0,0,1]] 输出:2 解释:已知学生 0 和学生 1 互为朋友,他们在一个朋友圈。 第2个学生自己在一个朋友圈。所以返回 2 。
示例2:
1 2 3 4 5 6 输入: [[1,1,0], [1,1,1], [0,1,1]] 输出:1 解释:已知学生 0 和学生 1 互为朋友,学生 1 和学生 2 互为朋友,所以学生 0 和学生 2 也是朋友,所以他们三个在一个朋友圈,返回 1 。
提示:
1 <= N <= 200
M[i][i] == 1
M[i][j] == M[j][i]
分析 首先分析输入数据,是无向图的邻接矩阵表示。找朋友圈个数也就是找该无向图中不同连通块的个数。
对于图的遍历,一般可以利用深度优先搜索(Depth First Search)、广度优先搜索(Breadth First Search)来解决。对于此问题,由于涉及分类、合并集合,还可以应用并查集(Union-Find Sets)。
深度优先搜索 DFS 深搜的过程:对于 i,j (0到N-1),当前任务是找 i 的朋友,如果M[i][j] == 1 (代表 i 和 j 是朋友),并且 j 没有被访问过,则标记 j 已访问,递归进行下一次深搜,找 j 的朋友;否则, j 自增直到 N-1,如此一直找到 i 所有的朋友都被标记。
所以,可以让 i 从0到 N-1 遍历,如果 i 没有被标记过,则继续递归深搜,并且记录朋友圈数加一。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 class Solution {public : int findCircleNum (vector<vector<int >>& M) { int N = M.size (); vector<int > visited (N, 0 ) ; int count = 0 ; for (int i = 0 ; i < N; ++i) { if (visited[i] == 0 ) { dfs (M, visited, i, N); ++count; } } return count; } void dfs (vector<vector<int >>& M, vector<int >& visited, int i, int N) { for (int j = 0 ; j < N; ++j) { if (M[i][j] == 1 && visited[j] == 0 ) { visited[j] = 1 ; dfs (M, visited, j, N); } } } };
时间复杂度:O(n2)
空间复杂度:O(n)
广度优先搜索 BFS 广搜和深搜思路差不多,只不过标记的顺序是按层次来的。利用队列就可以解决。
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 class Solution {public : int findCircleNum (vector<vector<int >>& M) { int N = M.size (); vector<int > visited (N, 0 ) ; int count = 0 ; queue<int > q; for (int i = 0 ; i < N; ++i) { if (visited[i] == 0 ) { q.push (i); while (!q.empty ()) { int s = q.front (); q.pop (); visited[s] = 1 ; for (int j = 0 ; j < N; ++j) { if (M[s][j] == 1 && visited[j] == 0 ) q.push (j); } } ++count; } } return count; } };
时间复杂度:O(n2)
空间复杂度:O(n)
并查集 Union-Find Sets 刚开始,有 N 个朋友圈,每个人一个朋友圈。如果两个人是朋友,就进行一次Merge(合并)操作,如果Merge成功,则朋友圈数量减一。最后的朋友圈数量就是需要的结果。
并查集需要实现两个方法,一个是Find,另一个是Merge。
Find(x) 用于查找x的根父节点。Merge(u, v) 判断u和v是否可以合并,如果可以,则合并u和v,返回True,否则返回False。
Find方法可以基于一个一维数组parent实现,使用路径压缩来优化。
1 2 3 4 5 6 7 8 9 10 11 12 int find (int x, vector<int >& parent) { int r = x; while (parent[r] != r) { r = parent[r]; } while (parent[x] != x) { int t = parent[x]; parent[x] = r; x = t; } return x; }
Merge方法很简单,利用Find来实现即可:
1 2 3 4 5 6 7 8 9 bool merge (int u, int v, vector<int >& parent) { int ru = find (u); int rv = find (v); if (ru == rv) { return false ; } parent[ru] = rv; return true ; }
准备工作时,需要对parent数组进行初始化:
1 2 3 4 5 6 void init (vector<int >& parent, int N) { parent.resize (N); for (int i = 0 ; i < N; i++) { parent[i] = i; } }
最后的代码:
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 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 class Solution {private : int find (int x) { int r = x; while (parent[r] != r) { r = parent[r]; } while (parent[x] != x) { int t = parent[x]; parent[x] = r; x = t; } return x; } bool merge (int u, int v) { int ru = find (u); int rv = find (v); if (ru == rv) { return false ; } parent[ru] = rv; return true ; } void init (int N) { parent.resize (N); for (int i = 0 ; i < N; i++) { parent[i] = i; } } vector<int > parent; public : int findCircleNum (vector<vector<int >>& M) { int N = M.size (); int ans = N; init (N); for (int i = 0 ; i < N; ++i) { for (int j = i+1 ; j < N; ++j) { if (M[i][j] && merge (i, j)) { ans --; } } } return ans; } };
上面的for循环是优化后的,考虑到无向图的邻接矩阵对角线对称,只用考虑一半即可。
时间复杂度:O(n2)
空间复杂度:O(n)
总结 本题不算难,但是可以使用多种算法去解决,值得思考,值得作为练手题。