用 Python 编写程序，在一组好友关系中查找好友组的数量

假设我们有一个好友列表，其中 friends[i] 是 i 的好友列表。友谊关系是双向的。每个人都是自己的好友，只要有一条共同好友路径将他们连接起来，两个人就属于一个好友组。我们必须找到朋友组的总数。

因此，如果输入为 friends = [[0, 1, 5],[1, 0],[2],[3, 4],[4, 3],[5, 0]]，则输出将为 3，因为三个朋友组如下所示 −

为了解决这个问题，我们将遵循以下步骤 −

• nodes := friends 的大小
• visited := 与节点大小相同的列表并填充 False
• ans := 0
• 定义一个函数 dfs() 。这将接受 vertex, accessed
• visited[vertex] := True
• 对于 friends[vertex] 中的每个 nei，执行
  • 如果 accessed[nei] 为 false，则
    • dfs(nei, accessed)
• 从主方法中，执行以下操作 −
• 对于范围为 0 到 nodes 的 i，执行
  • 如果 accessed[i] 为 false，则
    • dfs(i, visited)
    • ans := ans + 1
• 返回 ans

让我们看看下面的实现以便更好地理解 −

示例

class Solution:
   def solve(self, friends):
      nodes = len(friends)
      visited = [False for _ in range(nodes)]
      ans = 0
      def dfs(vertex, visited): visited[vertex] = True
         for nei in friends[vertex]:
            if not visited[nei]:
               dfs(nei, visited)
      for i in range(nodes):
         if not visited[i]:
            dfs(i, visited)
            ans += 1
      return ans
ob = Solution()
friends = [ [0, 1, 5], [1, 0], [2], [3, 4], [4, 3], [5, 0] ]
print(ob.solve(friends))

输入

[[0, 1, 5],
[1, 0],
[2],
[3, 4],
[4, 3],
[5, 0]
]

输出

3

相关文章

• Python - 使用交替的 0 和 1 初始化列表
• Python 中元组列表到字典的转换
• Python - 从两个列表中配对，使得成对的元素不相同
• 使用 Python 和 SQLite 的 SQL
• 使用 pytrie 模块在 Python 中进行前缀匹配
• 创建和访问 Python 包
• 如何使用正则表达式和数据类型选择多个 DataFrame 列
• 如何在 Pandas 中查找和过滤重复行?
• 用 Python 编写程序以正确的顺序查找机场?
• 如何在 Python Pandas 中使用字典顺序切片选择数据子集?

有用资源

• python 参考教程 - 该教程包含有关 python 的更多信息:https://www.cainiaomax.com/python/