Pythonの一連の友達接続で友達グループの数を見つけるプログラム

友達リストがあるとします。ここで、friends[i]は私が友達である人々のリストです。友情のつながりは双方向です。そして、それぞれの人は自分自身と友達であり、2人の人は、お互いをつなぐ相互の友達の道がある限り、友達グループに属します。友達グループの総数を見つける必要があります。

したがって、入力がfriends =[[0、1、5]、[1、0]、[2]、[3、4]、[4、3]、[5、0]]の場合、出力は3つの友達グループは以下のとおりです-

これを解決するには、次の手順に従います-

• ノード：=友達のサイズ
• 訪問：=ノードと同じサイズのリストでFalseで埋める
• ans：=0
• 関数dfs（）を定義します。これは頂点を取り、訪問します
• visited [vertex]：=True
• フレンズ[頂点]の各neiについて、
  • visited [nei]がfalseの場合、
    • dfs（nei、visited）
• メインの方法から、次の手順を実行します-
• ノードまでの範囲が0のiの場合は、
  • visited [i]がfalseの場合、
    • dfs（i、訪問済み）
    • ans：=ans + 1
• 回答を返す

理解を深めるために、次の実装を見てみましょう-

例

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