Chương trình tìm số nhóm bạn bè trong 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à người i kết bạn. Mối quan hệ bạn bè là hai chiều. Và mỗi người đều tự kết bạn với chính mình, hai người thuộc cùng một nhóm bạn bè miễn là tồn tại một đường đi các bạn chung kết nối họ. Chúng ta cần tìm tổng số nhóm bạn bè.

Ví dụ, nếu đầu vào là friends = [[0, 1, 5],[1, 0],[2],[3, 4],[4, 3],[5, 0]], thì đầu ra sẽ là 3, vì có ba nhóm bạn bè như sau:

Để giải quyết bài toán này, chúng ta thực hiện các bước sau:

• nodes := kích thước của mảng friends
• visited := một mảng cùng kích thước với nodes, khởi tạo tất cả giá trị là False
• ans := 0
• Định nghĩa hàm dfs() nhận tham số vertex và visited:
  • Đánh dấu visited[vertex] = True
  • Với mỗi nei trong friends[vertex]:
    • Nếu visited[nei] là False, gọi đệ quy dfs(nei, visited)
• Từ hàm chính, thực hiện:
  • Với i từ 0 đến nodes - 1:
    • Nếu visited[i] là False:
      • Gọi dfs(i, visited)
      • Tăng ans lên 1
• Trả về ans

Ví dụ triển khai

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