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

更新於：2020年11月19日

658 次瀏覽

開啟您的職業生涯

完成課程獲得認證

開始學習
廣告