Chương trình kiểm tra đồ thị có phải là rừng cây không trong Python

Cho đồ thị dưới dạng danh sách cạnh. Kiểm tra xem đồ thị có phải là tập hợp các cây (forest - không có chu trình) hay không.

Ví dụ: cạnh [[0,1],[0,2],[4,3]] → True (hai cây riêng biệt).

Giải thuật (DFS phát hiện chu trình)

1. Xây danh sách kề từ danh sách cạnh.
2. DFS từ mỗi nút chưa thăm:
   • Nếu gặp nút đã thăm (không phải cha) → có chu trình → .
   • Đánh dấu đã thăm, đệ quy các nút kề.
3. Nếu không phát hiện chu trình nào → .

Ví dụ minh họa

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

Đầu vào

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

Đầu ra

True