LeetCode 547. 朋友圈

在一个社交网络中，我们有一些好友关系，每个朋友是一个节点，节点之间可能存在双向好友关系。我们需要找出所有的朋友圈，并返回朋友圈的数量。

示例：

输入：[[1,2],[1,3],[0,1],[0,3],[0,4],[3,4]] 输出：3 解释：有三个朋友圈，分别是 [0,1,4]、[1,2,3] 和 [3,4] 。

解决方案：

这个问题可以使用深度优先搜索（DFS）来解决。我们可以遍历每个节点，并从该节点开始进行DFS，以找到所有与之相连的节点。每个访问过的节点都应该被标记为已访问，以避免重复计算。

以下是一个使用Python实现的DFS解决方案：

class Solution:
    def findCircleNum(self, M: List[List[int]]) -> int:
        n = len(M)
        visited = [False] * n
        def dfs(i):
            for j in range(n):
                if M[i][j] == 1 and not visited[j]:
                    visited[j] = True
                    dfs(j)
        
        count = 0
        for i in range(n):
            if not visited[i]:
                dfs(i)
                count += 1
        return count

扩展阅读：

• LeetCode 547. 朋友圈 Python 代码示例
• 深度优先搜索（DFS）算法详解

图片：