Chương trình phân chia người thành hai nhóm sao cho kẻ thù không cùng nhóm bằng Python

Giả sử chúng ta có số n và ma trận 2D enemies. n chỉ ra có n người được đánh số từ 0 đến n-1. Mỗi hàng trong enemies chứa cặp [a, b] nghĩa là a và b là kẻ thù. Cần kiểm tra xem có thể chia n người thành hai nhóm sao cho không có cặp kẻ thù nào cùng nhóm hay không.

Ví dụ, nếu n = 4, enemies = [[0, 3], [3, 2]], thì đầu ra là True, vì có thể chia thành [0, 1, 2] và [3].

Quy trình giải quyết

1. Xây dựng đồ thị kề từ danh sách enemies.
2. Dùng DFS để tô màu đồ thị hai màu (0 và 1).
3. Nếu phát hiện xung đột (hai nút kề cùng màu), trả về False.
4. Nếu tô màu thành công cho tất cả các thành phần liên thông, trả về True.

Ví dụ mã nguồn

class Solution:
    def solve(self, n, enemies):
        from collections import defaultdict
        graph = defaultdict(list)
        for u, v in enemies:
            graph[u].append(v)
            graph[v].append(u)
        color = {}
        def dfs(u, c=0):
            if u in color:
                return color[u] == c
            color[u] = c
            return all(dfs(v, c ^ 1) for v in graph[u])
        return all(dfs(u) for u in range(n) if u not in color)

ob = Solution()
n = 4
enemies = [[0, 3], [3, 2]]
print(ob.solve(n, enemies))  # Output: True

Đầu vào

4, [[0, 3], [3, 2]]

Đầu ra

True