547. 朋友圈(Easy)

题目描述

给定一个二维的 0-1 矩阵，如果第 (i, j) 位置是 1，则表示第 i 个人和第 j 个人是朋友。已知 朋友关系是可以传递的，即如果 a 是 b 的朋友，b 是 c 的朋友，那么 a 和 c 也是朋友，换言之这 三个人处于同一个朋友圈之内。求一共有多少个朋友圈。

样例

Input: [[1,1,0],
        [1,1,0], 
        [0,0,1]] 
Output: 2

题解

深度搜索的经典应用

• 主函数：遍历还没有加入朋友圈的人 m
• 父函数：遍历 m 的朋友圈

Python示例

# 遍历 i 的 朋友圈
def findFriends(M, i, visited):
        visited.append(i)
        for k in range(len(M)):
            if k not in visited and M[k][i] == 1:
                findFriends(M, k, visited)
class Solution:
    def findCircleNum(self, M: List[List[int]]) -> int:    
        visited = []
        ans = 0
        for i in range(len(M)): # 按人头遍历，找到没有加入朋友圈的人 i 
            if i not in visited: 
                findFriends(M, i, visited) 
                ans += 1
        return ans

Go 示例

func findCircleNum(isConnected [][]int) int {
    n := len(isConnected)
    res := 0
    visited := make([]bool, n)
    var dfs func(int) 
    dfs = func(city int) {
        visited[city] = true
        for nextCity := 0; nextCity < n; nextCity++ {
            if !visited[nextCity] && isConnected[city][nextCity] == 1 {
                dfs(nextCity)
            }
        }
    }

    for i := 0; i < n; i++ {
        if !visited[i] {
            dfs(i)
            res ++
        }
    }
    return res
}