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

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

ดังนั้นหากอินพุตเป็น n =4 ศัตรู =[[0, 3],[3, 2]] ผลลัพธ์จะเป็น True เนื่องจากเราสามารถมีสองกลุ่มนี้ [0, 1, 2] และ [ 3].

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กราฟ :=รายการที่อยู่ติดกันที่ว่างเปล่า

• สำหรับแต่ละคู่ศัตรู (u, v) ในตัวศัตรู ทำ

  • แทรก v ที่ส่วนท้ายของกราฟ[u]

  • ใส่ u ที่ท้ายกราฟ[v]

• สี :=แผนที่ใหม่

• กำหนดฟังก์ชัน dfs() นี่จะใช้เวลา u, c :=0 เริ่มแรก

• ถ้าคุณอยู่ในสีแล้วล่ะก็

  • คืนค่าจริงเมื่อ color[u] เหมือนกับ c

• สี[u] :=c

• คืนค่า จริง เมื่อ dfs(v, c XOR 1) ทั้งหมด สำหรับแต่ละ v ในกราฟ[u] เป็นจริง

• จากวิธีหลักให้ทำดังต่อไปนี้ -

• คืนค่า จริง เมื่อทั้งหมด (dfs(u) สำหรับแต่ละ u ในช่วง 0 ถึง 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))

อินพุต

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

ผลลัพธ์

True