グラフ理論を理解する(2) 典型的な問題を解く

グラフ理論に関する典型的な問題をChatGPTに作成してもらった。

問題：秘密ネットワークの検出
解決のヒント
1. ステップ1：すべてのノードから都市Cに到達できるか？
2. ステップ2：都市Cがループに含まれているか？
判定の流れ
完成コード（DFSでループ判定あり）

問題：秘密ネットワークの検出

問題文

ある国では、都市と都市を結ぶ秘密の通信回線が存在します。これらの回線は一方向のみ使えるため、一方通行のグラフと考えられます。

政府は、「どの都市からでも特定の都市Cに秘密の通信が届くかどうか」を調査したいと考えています。

さらに、都市Cが自ら再び通信を発信できるループ構造を持っているかも重要です。
すべての都市から都市Cに到達でき、かつ都市Cが含まれるループが存在するなら、「監視可能」とみなされます。

入力

N M C
a_1 b_1
a_2 b_2
...
a_M b_M

N: 都市の数 (1 ≦ N ≦ 10,000)
M: 通信回線の数 (1 ≦ M ≦ 50,000)
C: 注目している都市の番号 (1 ≦ C ≦ N)
続く M 行では、それぞれ a_i → b_i という回線の情報（1-indexed）

出力

監視可能

または

監視不能

条件

すべての都市から都市 C に到達できる
都市 C が含まれるサイクルが存在する（例：C → X → … → C）

この2つを同時に満たす場合に限り「監視可能」と出力、それ以外は「監視不能」とする。

入力例1

出力例1

監視可能

すべての都市から 3 に到達可能。かつ 3→1→2→3 でループあり。

入力例2

出力例2

監視不能

5から3には戻れない。しかもループもない。

解決のヒント

ステップ1：すべてのノードから都市Cに到達できるか？

グラフを逆向きに考えてください（辺を反転）
C から逆向きに DFS または BFS を行い、何個のノードに到達できるかを確認
- 逆に言えば「全ノードから C に行ける」 ⇔ 「逆グラフで C から全ノードをたどれる」

→ 逆グラフを使って C から逆に DFS → 到達した数が N ならOK

ステップ2：都市Cがループに含まれているか？

C を含むループが存在するというのは、C から始めてどこかを経由し、再び C に戻って来られることを意味します
C から DFS して、再び C に戻ってこられるかチェックすればよい（または SCC を使っても良い）

→ 通常のグラフで DFS/BFS。C → … → C となるパスがあるか確認

※自分自身に自己ループがある（例：C → C）もOK

判定の流れ

逆グラフを作る
逆グラフで C からDFSし、すべてのノードにたどり着けるかを確認（→ すべての都市からCへ到達可能か）
元のグラフで C から DFSして、C に戻ってこられるか（ループがあるか）確認
両方満たす → "監視可能"、どちらか1つでも欠けている → "監視不能"

完成コード（DFSでループ判定あり）

t = """
5 6 3
1 2
2 3
3 4
4 5
5 2
3 1
"""

# t = """
# 5 4 3
# 1 2
# 2 3
# 3 4
# 4 5
# """

l_t = t.strip().split('\n')

N, M, C = map(int, l_t[0].split(" "))
l_a = []
l_b = []
for i in range(M):
    a, b = map(int, l_t[i+1].split(" "))
    l_a.append(a)
    l_b.append(b)

# --- 逆グラフ（Cに向かう）
reverse_graph = {}
for a, b in zip(l_a, l_b):
    if b not in reverse_graph:
        reverse_graph[b] = []
    reverse_graph[b].append(a)

def reachable_from_all_to_C(c):
    visited = set([c])
    def dfs(v):
        for neighbor in reverse_graph.get(v, []):
            if neighbor not in visited:
                visited.add(neighbor)
                dfs(neighbor)
    dfs(c)
    return len(visited) == N

# --- 正方向のグラフ（Cから出発）
graph = {}
for a, b in zip(l_a, l_b):
    if a not in graph:
        graph[a] = []
    graph[a].append(b)

def has_cycle_from_C(c):
    visited = set()
    def dfs(v):
        for neighbor in graph.get(v, []):
            if neighbor == c:
                return True
            if neighbor not in visited:
                visited.add(neighbor)
                if dfs(neighbor):
                    return True
        return False
    visited.add(c)
    return dfs(c)

# --- 判定
if reachable_from_all_to_C(C) and has_cycle_from_C(C):
    print("監視可能")
else:
    print("監視不能")

今回はdfsを使って検索をしたが、bfsでも同じになる。ただし、どっちが先に見つけるかの問題で、ものによっては解決までの時間が異なる。