在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)
- 如果visited [nei]是False,那么
- 在主方法中,执行以下操作-。
- 对于i在0到节点的范围内,执行以下操作-。
- 如果visited [i]是False,那么
- dfs (i,visited)
- ans:= ans + 1
- 如果visited [i]是False,那么
- 返回ans
看下面的示例实现以更好的理解−
更多Python相关文章,请阅读:Python 教程