Route Between Nodes

# 問題

有向グラフと 2 頂点が与えられたとき，その 2 頂点間にパスがあるか判定せよ．

# 答え

探索するだけ

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
N = int(input()) # number of nodes
M = int(input()) # number of edges

start = int(input())
goal = int(input())

G = [[] for _ in range(N)]
for _ in range(M):
    u, v = map(int, input(),split())
    G[u].append(v)
    # G[v].append(u) # for undirected

has_visited = set()
def DFS(graph, node):
    has_visited.add(node)
    for neighbor in graph[node]:
        if neighbor in has_visited:
            continue
        else:
            DFS(graph, neighbor)

DFS(G, start)

if goal in has_visited:
    print("reachable")
else:
    print("unreachable")