โปรแกรมนับจำนวนสัตว์น้อยที่สุดที่ไม่มีผู้ล่าใน Python

สมมติว่าเรามีรายการตัวเลข nums โดย nums[i] แสดงผู้ล่าของสัตว์ตัวที่ i และถ้าไม่มีผู้ล่าจะเก็บค่า -1 เราต้องหาจำนวนกลุ่มน้อยที่สุดของสัตว์ โดยที่ไม่มีสัตว์ตัวใดอยู่ในกลุ่มเดียวกับผู้ล่าตรงๆ หรือผู้ล่าอ้อมๆ ของมัน

ตัวอย่าง: nums = [1, 2, -1, 4, 5, -1] ผลลัพธ์คือ 3 สามารถจัดกลุ่มได้เป็น [0, 3], [1, 4], [2, 5]

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

1. ถ้า A ว่าง คืนค่า 0
2. สร้าง adj เป็นแผนที่ (map) ว่าง, vis เป็นเซตใหม่, roots เป็นลิสต์ใหม่
3. วนลูปแต่ละ index i และค่า a ใน A:
   • ถ้า a == -1 เพิ่ม i เข้า roots
   • เพิ่ม a เข้า adj[i] และเพิ่ม i เข้า adj[a]
4. กำหนด best = -infinity
5. สำหรับแต่ละ root ใน roots:
   • สร้างสแต็ก stk ใส่ [root, 1]
   • วนลูป while stk ไม่ว่าง:
     • นำ (node, d) ออกจากสแต็ก
     • ถ้า node อยู่ใน vis หรือ node == -1 ให้ข้าม
     • best = max(best, d)
     • เพิ่ม node เข้า vis
     • สำหรับแต่ละ u ใน adj[node] ใส่ (u, d + 1) เข้า stk
6. คืนค่า best

ตัวอย่างโค้ด Python

from collections import defaultdict

class Solution:
    def solve(self, A):
        if not A:
            return 0
        adj = defaultdict(list)
        vis = set()
        roots = []
        for i, a in enumerate(A):
            if a == -1:
                roots.append(i)
            adj[i].append(a)
            adj[a].append(i)
        best = -float("inf")
        for root in roots:
            stk = [(root, 1)]
            while stk:
                node, d = stk.pop()
                if node in vis or node == -1:
                    continue
                best = max(best, d)
                vis.add(node)
                for u in adj[node]:
                    stk.append((u, d + 1))
        return best

ob = Solution()
nums = [1, 2, -1, 4, 5, -1]
print(ob.solve(nums))  # Output: 3

อินพุต / เอาต์พุต

Input: [1, 2, -1, 4, 5, -1]

Output: 3