LeetCode547. Friend Circles

1、题目链接

https://leetcode.com/problems/friend-circles/

2、解题思路

这道题的意思是说给你一个二维数组M，这个二维数组表示两两之间有没有存在朋友关系，比如M[i][j] = 1 的话，就表示i和j是朋友关系，而且这种关系是可以传递的，比如i和j是朋友关系，j和k也是朋友关系，那么可以理解为i和k也是朋友关系；这是一道比较经典的并查集算法问题，并查集算法通常是为了解决 “动态连通性” 这一类问题；这道题我们可以用一个递归来实现，首先我们从第一个人A开始遍历，搜索他的朋友圈关系，如果他和某个人B有朋友关系，那么我们接着搜索B的朋友圈关系，如果到最后搜索到没有关系了就返回，那么问题来了，这样搜索的话我们可能会重复，因为如果在搜索B的朋友圈关系的时候，A已经是B的朋友了，且A已经被搜索过了，那么这样的话我们就需要一个标识位去记录是否搜索过某一个人，等到递归返回的时候就代表条完整的朋友链已经搜索完成，总的朋友圈数量+1即可。

3、代码

• Java

public int findCircleNum(int[][] M) {
    if (null == M || M.length == 0) {
        return 0;
    }
    boolean[] connected = new boolean[M.length];  //记录是否查询过某一个朋友
    int friendCircleCount = 0;  //朋友圈总数
    for (int i = 0; i < M.length; i++) {
        if (connected[i]) {
            continue;
        }
        searchConnected(i, M, connected);
        friendCircleCount++;
    }
    return friendCircleCount;
}
public void searchConnected(int parent, int[][] M, boolean[] connected) {
    connected[parent] = true;
    for (int i = 0; i < M.length; i++) {
        //如果当前朋友没有被查询过，且与上一位查询的朋友存在关系，那么就搜索当前朋友的朋友圈关系
        if (!connected[i] && M[parent][i] == 1) {
            searchConnected(i, M, connected);
        }
    }

• Python

由于太忙，后续补上

• JavaScript

由于太忙，后续补上

4、提交结果