DFS: Does a Path Exist

DFS: is there a path from s to t

Read a directed graph and two vertices s, t, and decide whether there is a directed path from s to t. Print 1 if reachable, 0 otherwise.

Complete dfs: starting at v, mark every reachable vertex in visited[]. The main function calls dfs(s) and then checks whether visited[t] is true.

Pitfalls: (1) mark visited[v] on entry, or a cyclic graph recurses forever and overflows the stack. (2) Only recurse into neighbours with adj[v][w]==1 && !visited[w]. (3) When s == t the answer is 1 (dfs(s) marks s itself, so visited[t] is true).

Input

• Line 1: V E.
• Next E lines: u v, a directed edge u → v.
• Last line: s t.

Output

• One line: 1 (reachable) or 0 (not).

Example: input 4 2 / 0 1 / 1 2 / 0 2 -> 1 (0→1→2 reaches 2).