โปรแกรมแยกบุคคลไม่ให้ศัตรูอยู่ในกลุ่มเดียวกันด้วย Python

สมมติว่าเรามีตัวเลข n และเมทริกซ์ 2 มิติชื่อ enemies โดย n แสดงว่ามีคน n คน ติดป้ายกำกับจาก [0, n - 1] แต่ละแถวใน enemies มีค่า [a, b] หมายความว่า a และ b เป็นศัตรูกัน เราต้องตรวจสอบว่าสามารถแบ่งคน n คนออกเป็นสองกลุ่มได้หรือไม่ โดยที่ไม่มีศัตรูสองคนอยู่ในกลุ่มเดียวกัน



ตัวอย่าง: n = 4, enemies = [[0, 3], [3, 2]] ผลลัพธ์คือ True เพราะสามารถแบ่งได้เป็น [0, 1, 2] และ [3]

ขั้นตอนการแก้ปัญหา

สร้าง graph เป็นรายการความติดกัน (adjacency list) ว่าง
สำหรับแต่ละคู่ศัตรู (u, v) ใน enemies:

เพิ่ม v เข้า graph[u]
เพิ่ม u เข้า graph[v]


สร้าง color เป็นแผนที่ใหม่
กำหนดฟังก์ชัน dfs(u, c=0):

ถ้า u อยู่ใน color คืนค่า color[u] == c
color[u] = c
คืนค่า True ถ้า dfs(v, c ^ 1) เป็นจริงสำหรับทุก v ใน graph[u]


จากเมธอดหลัก คืนค่า True ถ้า dfs(u) เป็นจริงสำหรับทุก u ในช่วง 0 ถึง n-1 ที่ยังไม่อยู่ใน color


ตัวอย่างโค้ด Python
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


อินพุต / เอาต์พุต
Input: 4, [[0, 3], [3, 2]]
Output: True