โปรแกรมตรวจสอบว่า Graph เป็น Forest (ชุดของ Trees) หรือไม่ใน Python

สมมติว่าเรามีกราฟในรูป edge list เราต้องตรวจสอบว่ามันเป็น forest (ชุดของต้นไม้ ไม่มี cycle) หรือไม่

ตัวอย่าง: edges = [[0,1],[0,2],[4,3]] เป็น forest (มี 2 ต้นไม้) ผลลัพธ์ True

ขั้นตอนการแก้ปัญหา (DFS Cycle Detection)

1. สร้าง adjacency list e จาก edges
2. seen = set()
3. ฟังก์ชัน dfs(node, prev):
   • หาก node in seen คืน False (เจอ cycle)
   • เพิ่ม node เข้า seen
   • สำหรับเพื่อนบ้าน adj ใน e[node]:
     • หาก adj != prev และ dfs(adj, node) เป็น False คืน False
   • คืน True
4. สำหรับทุกโหนดใน e: หากยังไม่ seen และ dfs(node, -1) เป็น False คืน False
5. คืน True

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

from collections import defaultdict

class Solution:
    def solve(self, edges):
        e = defaultdict(list)
        for u, v in edges:
            e[u].append(v)
            e[v].append(u)
        
        seen = set()
        
        def dfs(node, prev):
            if node in seen:
                return False
            seen.add(node)
            for adj in e[node]:
                if adj != prev:
                    if not dfs(adj, node):
                        return False
            return True
        
        for node in e:
            if node not in seen and not dfs(node, -1):
                return False
        return True

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

อินพุต

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

เอาต์พุต

True