在Python中查找一组朋友连接中朋友组数的程序

假设我们有一个朋友列表，其中friends [i]是i和他人交上的朋友列表。朋友关系是双向的。 每个人都是自己的朋友，只要两个人之间有一条互相朋友连接的路径，他们就在一个朋友组中。我们要找出朋友组的总数。

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

为了解决这个问题，我们将按照以下步骤进行−

• 节点:=朋友的大小
• visited:=大小与节点相同的列表，并且填充为False
• ans:=0
• 定义一个函数dfs()。这将采用顶点，visited
• visited [vertex]：= True
• 对于friends[vertex]中的每个nei，进行如下操作-
  • 如果visited [nei]是False，那么
    • dfs（nei，visited）
• 在主方法中，执行以下操作-。
• 对于i在0到节点的范围内，执行以下操作-。
  • 如果visited [i]是False，那么
    • dfs (i，visited)
    • ans：= ans + 1
• 返回ans

看下面的示例实现以更好的理解−

更多Python相关文章，请阅读：Python 教程

示例

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