グラフ理論に関する典型的な問題をChatGPTに作成してもらった。
問題：秘密ネットワークの検出
問題文
ある国では、都市と都市を結ぶ秘密の通信回線が存在します。これらの回線は一方向のみ使えるため、一方通行のグラフと考えられます。
政府は、「どの都市からでも特定の都市Cに秘密の通信が届くかどうか」を調査したいと考えています。
さらに、都市Cが自ら再び通信を発信できるループ構造を持っているかも重要です。
すべての都市から都市Cに到達でき、かつ都市Cが含まれるループが存在するなら、「監視可能」とみなされます。
入力
N M C
a_1 b_1
a_2 b_2
...
a_M b_MN: 都市の数 (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
5 6 3
1 2
2 3
3 4
4 5
5 2
3 1出力例1
監視可能すべての都市から 3 に到達可能。かつ 3→1→2→3 でループあり。
入力例2
5 4 3
1 2
2 3
3 4
4 5出力例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でも同じになる。ただし、どっちが先に見つけるかの問題で、ものによっては解決までの時間が異なる。
コメント