Python程序：查找朋友连接集中朋友群组的数量

假设我们有一个朋友列表，其中friends[i]是第i个人朋友的列表。朋友关系是双向的。每个人都是自己的朋友，只要存在连接两个人的朋友的路径，这两个朋友就属于同一个朋友群组。我们需要找到朋友群组的总数。

因此，如果输入类似于friends = [[0, 1, 5],[1, 0],[2],[3, 4],[4, 3],[5, 0]]，则输出为3，因为朋友群组如下所示：

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

• nodes := friends 的大小
• visited := 一个与nodes大小相同并填充为False的列表
• ans := 0
• 定义一个函数dfs()。它将接收顶点和visited
• visited[vertex] := True
• 对于friends[vertex]中的每个nei：
  • 如果visited[nei]为false，则
    • dfs(nei, visited)
• 在主方法中，执行以下操作：
• 对于范围从0到nodes的i：
  • 如果visited[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

Arnab Chakraborty

更新于：2020年11月19日

658 次浏览

开启您的职业生涯

完成课程获得认证

开始学习