LeetCode
朋友圈
班上有 N 名学生。其中有些人是朋友，有些则不是。他们的友谊具有是传递性。如果已知 A 是 B 的朋友，B 是 C 的朋友，那么我们可以认为 A 也是 C 的朋友。所谓的朋友圈，是指所有朋友的集合。
给定一个 N * N 的矩阵 M，表示班级中学生之间的朋友关系。如果M[i][j] = 1，表示已知第 i 个和 j 个学生互为朋友关系，否则为不知道。你必须输出所有学生中的已知的朋友圈总数。
示例 1:
输入:
[[1,1,0],
[1,1,0],
[0,0,1]]
输出: 2
说明：已知学生0和学生1互为朋友，他们在一个朋友圈。
第2个学生自己在一个朋友圈。所以返回2。
示例 2:
输入:
[[1,1,0],
[1,1,1],
[0,1,1]]
输出: 1
说明：已知学生0和学生1互为朋友，学生1和学生2互为朋友，所以学生0和学生2也是朋友，所以他们三个在一个朋友圈，返回1。
解法1：并查集
解题思路：
我们用并查集表示每一个朋友圈，一个人就代表一个朋友圈，当我们发现输入的i,j分属两个不同的朋友圈时，我们就将两个朋友圈合并，这就是并查集的解法
class Solution {
public int findCircleNum(int[][] M) {
int N = M.length;
int[] parent = new int[N];
Arrays.fill(parent,-1);
int res = N; //朋友圈的个数首先是所有人的个数，也就是对角线的长度
for(int i=0; i<N; i++)
for(int j=0; j<N; j++)
if(M[i][j]==1)
{
if(union_root(i,j,parent)==1)
//两个人不属于同一个朋友圈，那就将两个朋友圈合并，总数减1
res--;
}
return res;
}
public int find_root(int x, int[] parent)
{
int x_root = x;
while(parent[x_root]!=-1)
x_root = parent[x_root];
return x_root;
}
public int union_root(int x, int y, int[] parent)
{
int x_root = find_root(x,parent);
int y_root = find_root(y,parent);
if(x_root==y_root)
return 0;
parent[x_root] = y_root;
return 1;
}
}
时间复杂度为O(n^3) : 因为除了遍历M数组外，我们还需要遍历parent数组，所以复杂度为三次方
空间复杂度为O(N) : parent数组的大小
解法2：dfs
解题思路：
如果我们把输入的矩阵看作一个图，那么连通块的个数就是我们能够进行深搜的次数
public class Solution {
public void dfs(int[][] M, int[] visited, int i) {
for (int j = 0; j < M.length; j++) {
if (M[i][j] == 1 && visited[j] == 0) {
visited[j] = 1;
dfs(M, visited, j);
}
}
}
public int findCircleNum(int[][] M) {
int[] visited = new int[M.length];
int count = 0;
for (int i = 0; i < M.length; i++) {
if (visited[i] == 0) {
dfs(M, visited, i);
count++;
}
}
return count;
}
}
时间复杂度为O(n^2):遍历一次二维数组
空间复杂度为O(n):visited数组的大小
解法3：bfs
解题思路：
跟深搜是一样的，就是从一个结点出发，访问它能连通的所有结点，当它所有连通结点访问完时，发现还有结点没访问，说明是不连通的，因此朋友圈的个数要增加，总而言之就是换了一种搜索方式
public class Solution {
public int findCircleNum(int[][] M) {
int[] visited = new int[M.length];
int count = 0;
Queue < Integer > queue = new LinkedList < > ();
for (int i = 0; i < M.length; i++) {
if (visited[i] == 0) {
queue.add(i);
while (!queue.isEmpty()) {
int s = queue.remove();
visited[s] = 1;
for (int j = 0; j < M.length; j++) {
if (M[s][j] == 1 && visited[j] == 0)
queue.add(j);
}
}
count++;
}
}
return count;
}
}
复杂度是一样的
