Chương trình tìm số lượng nhóm bạn trong một tập hợp các kết nối bạn bè bằng Python

Giả sử chúng ta có một danh sách bạn bè, trong đó friends [i] là danh sách những người mà tôi kết bạn. Sự kết nối của tình bạn là hai chiều. Và mỗi người là bạn với chính mình và hai người ở trong một nhóm bạn miễn là có một con đường bạn chung nào đó kết nối họ. Chúng ta phải tìm tổng số nhóm bạn.

Vì vậy, nếu đầu vào giống như friends =[[0, 1, 5], [1, 0], [2], [3, 4], [4, 3], [5, 0]], thì đầu ra sẽ là 3, vì Ba nhóm bạn như bên dưới -

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• các nút:=số lượng bạn bè
• đã thăm:=một danh sách có kích thước tương tự như các nút và điền bằng Sai
• ans:=0
• Định nghĩa một hàm dfs (). Điều này sẽ đạt đến đỉnh, đã thăm
• đã thăm [vertex]:=True
• đối với mỗi nei trong bạn bè [vertex], hãy thực hiện
  • nếu đã thăm [nei] là sai, thì
    • dfs (nei, đã thăm)
• Từ phương pháp chính, hãy thực hiện như sau -
• đối với tôi trong phạm vi 0 đến các nút, hãy thực hiện
  • nếu đã thăm [i] là sai, thì
    • dfs (tôi, đã ghé thăm)
    • ans:=ans + 1
• trả lại ans

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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))

Đầu vào

[[0, 1, 5],
[1, 0],
[2],
[3, 4],
[4, 3],
[5, 0]
]

Đầu ra

3