Before finding an order, learn to check one.
What to build
A program that checks whether a proposed order of tasks follows every rule.
Requirements
- Record the position of each task in the proposed order.
- Check every rule against those positions.
- Print
yesif every rule is kept, and otherwiseno.
Input
The first line has n and m. Each of the next m lines has a rule u v, which means u must come before v. The last line has the n tasks in the proposed order, each once.
Output
yes or no.
Constraints
1 ≤ n ≤ 100 and 0 ≤ m ≤ 1000.
Example
Input:
4 3
0 1
1 2
0 3
0 3 1 2
Output:
yes
Why it works
A topological order is defined by its edges all pointing forward, so checking each edge against the positions is the whole test. It takes O(n + m) time.
Examples
Example 1 · Input
4 3 0 1 1 2 0 3 0 3 1 2
Expected output
yes
Example 2 · Input
4 3 0 1 1 2 0 3 1 0 2 3
Expected output
no
Hints
Hint 1
Make an array `pos`, where `pos[t]` is where task `t` appears in the proposed order.
Hint 2
A rule `u v` is kept exactly when `pos[u] < pos[v]`.
Solution
Show one correct solution (try it yourself first)
#include <stdio.h>
int main(void) {
int n, m, u[1000], v[1000], t, pos[100];
scanf("%d %d", &n, &m);
for (int i = 0; i < m; i++) scanf("%d %d", &u[i], &v[i]);
for (int i = 0; i < n; i++) {
scanf("%d", &t);
pos[t] = i;
}
int ok = 1;
for (int i = 0; i < m; i++)
if (pos[u[i]] > pos[v[i]]) ok = 0;
printf("%s\n", ok ? "yes" : "no");
return 0;
}