首页 > 上网技巧 > Leetcode547: Friend Circles 朋友圈问题

Leetcode547: Friend Circles 朋友圈问题

时间:2020-12-19 21:35 作者:QQ地带 我要评论

 问题描述

在一个班级里有N个同学, 有些同学是朋友,有些不是。他们之间的友谊是可以传递的比如A和B是朋友,B和C是朋友,那么A和C也是朋友。我们定义 friend circle为由直接或者间接都是朋友组成的group.
 
给定N*N 数组 M 代表同学之间的关系. 如果M[i][j] = 1, 那么i 和 j 同学是朋友,现在我们需要输出friend circles 的数量
 
Example 1:
Input:
[[1,1,0],
[1,1,0],
[0,0,1]]
Output: 2
解释: 0和1号同学是朋友,所以他们是一个friend cricle,2号同学自己是个friend circle,所有返回2。
 
Example 2:
Input:
[[1,1,0],
[1,1,1],
[0,1,1]]
Output: 1
解释: 0号同学和1号同学是朋友,1号和2号同学是朋友,那么0,1,2都是朋友,他们组成一个friend circle,所以结果返回1
 
Note
N is in range [1,200].
M[i][i] = 1 for all students.
If M[i][j] = 1, then M[j][i] = 1.
 
分析
我们可以将给定的M数组看做是一个graph, M[i][j] = 1 表示节点i 和 j 相连,那么寻找fridend circle的问题,转化为图遍历的问题,求fiend circle的个数实则为求连通图的个数。解决这类问题通常使用DFS或者BFS去更新一个visited数组,对每个未访问的节点调用图形遍历算法,每次调用,所有相连节点的状态都会被更新,那么friend cicle的数量则为调用遍历的次数。
 
DFS实现
public int findCircleNum(int[][] M) {
        int N = M.length;
        boolean[] visited = new boolean[N];
        int cnt = 0;
        for(int i = 0; i < N; i++){
            if(!visited[i]){
                dfs(M, visited, i);
                cnt++;
            }
        }
        return cnt;
    }
    
    private void dfs(int[][] M, boolean[] visited, int i){
        visited[i] = true;
        for(int j = 0; j < M.length; j++){
            if(M[i][j] == 1 && !visited[j]){
                dfs(M, visited, j);
            }
        }
    }
时间复杂度:O(n^2),总体上要遍历M数组的所有位置
空间复杂度:O(n)
 
BFS实现
   public int findCircleNum(int[][] M) {
        boolean[] visited = new boolean[M.length];
        int count = 0;
        Queue < Integer > queue = new LinkedList < > ();
        for (int i = 0; i < M.length; i++) {
            if (!visited[i]) {
                queue.add(i);
                while (!queue.isEmpty()) {
                    int s = queue.remove();
                    visited[s] = true;
                    for (int j = 0; j < M.length; j++) {
                        if (M[s][j] == 1 && !visited[j]])
                            queue.add(j);
                    }
                }
                count++;
            }
        }
        return count;
    }
时间复杂度:O(n^2),总体上要遍历M数组的所有位置
空间复杂度:O(n)
 
 

标签: LeetCode
顶一下
(0)
0%
踩一下
(0)
0%

Google提供的广告