Decide whether there is a path between two vertices of an undirected graph.
What to build
A depth-first search that answers one reachability question.
Requirements
- Run a depth-first search from vertex
s. - Print
yesif vertextcan be reached froms, andnoif it cannot. - A vertex can always reach itself.
Input
The first line has n and m. Each of the next m lines has an edge u v. The last line has s and t.
Output
yes or no.
Constraints
1 ≤ n ≤ 50 and 0 ≤ m ≤ 1000.
Example
Input:
5 3
0 1
1 2
3 4
0 2
Output:
yes
Why it works
Depth-first search marks every vertex that has a path from the start, and no others. The visited marks stop it going round a cycle for ever.
Examples
Example 1 · Input
5 3 0 1 1 2 3 4 0 2
Expected output
yes
Example 2 · Input
5 3 0 1 1 2 3 4 0 4
Expected output
no
Hints
Hint 1
Write a recursive dfs(u) that marks u as visited.
Hint 2
Inside dfs, call dfs(v) for every neighbour v that is not visited yet.
Hint 3
After dfs(s) finishes, t can be reached exactly when it is marked.
Solution
Show one correct solution (try it yourself first)
#include <stdio.h>
int adj[50][50], visited[50];
int n;
void dfs(int u) {
visited[u] = 1;
for (int v = 0; v < n; v++) {
if (adj[u][v] && !visited[v]) dfs(v);
}
}
int main(void) {
int m, s, t;
scanf("%d %d", &n, &m);
for (int i = 0; i < m; i++) {
int u, v;
scanf("%d %d", &u, &v);
adj[u][v] = 1;
adj[v][u] = 1;
}
scanf("%d %d", &s, &t);
dfs(s);
if (visited[t]) printf("yes\n");
else printf("no\n");
return 0;
}