【Python】グラフが木の集合（フォレスト）かどうかを判定するプログラム

問題概要

辺のリストとして表されたグラフが与えられたとき、そのグラフが木の集合（フォレスト）であるかどうかを判定します。

たとえば、入力が下図のような場合、出力は True になります。

グラフがフォレストであるためには、すべての連結成分が木であり、閉路（サイクル）が一切存在しないことが必要です。そこで、深さ優先探索（DFS）を用いて各連結成分を調べます。

解法の考え方

DFSの探索中に、すでに訪問済みのノードへ再び到達した場合、閉路が存在すると判断できます。ただし、無向グラフでは直前にいた親ノードへの「逆戻り」は必ず発生するため、このケースは除外して判定します。

アルゴリズムの手順

1. 関数 dfs() を定義します。引数は現在のノード node と直前のノード prev です。

2. node がすでに seen に含まれている場合は False を返します（閉路が検出されたことを意味します）。

3. node を seen に追加します。

4. e[node] 内の各隣接ノード n について、n が prev と異なる場合に dfs(n, node) を呼び出し、その結果が False なら False を返します。

5. すべての隣接ノードの探索が完了したら True を返します。

メイン処理の手順

1. 空のマップ（隣接リスト）e を用意します。

2. edges 内の各辺の始点 u と終点 v について、e[u] の末尾に v を、e[v] の末尾に u をそれぞれ追加します。

3. 新しい集合 seen を用意します。

4. e 内の各ノードについて、まだ訪問しておらず、かつ dfs(node, -1) が False を返す場合は False を返します。

5. すべてのノードの確認が完了したら True を返します。

以下の実装例を見ると、より理解が深まるでしょう。

実装例

from collections import defaultdict

class Solution:
    def solve(self, edges):
        e = defaultdict(list)
        for t, f in edges:
            e[t].append(f)
            e[f].append(t)

        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))

入力

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

出力

True

補足：動作のポイント

• この例では、{0, 1, 2} からなる木と {3, 4} からなる木という2つの独立した木が存在するため、グラフ全体がフォレストとなり、結果は True になります。

• もしグラフ内に閉路が1つでも存在すれば、DFSが訪問済みノードに再到達した時点で False が返されます。

• 計算量は DFS ベースのため O(V + E)（Vは頂点数、Eは辺数）であり、効率的に判定できます。