There are n tasks, numbered 0 to n - 1, and m rules u v, each meaning task u must be done before task v. Print an order of all the tasks that follows every rule. When several tasks are ready, take the smallest-numbered one first, so the answer is unique. If no order exists, print cycle.
What to build
A program that puts tasks in an order that follows every rule.
Requirements
- Count each task's in-degree.
- Repeatedly take the smallest-numbered task that is ready.
- Print
cycleif at some point no task is ready.
Input
The first line has n and m (1 ≤ n ≤ 100, 0 ≤ m ≤ 1000). Each of the next m lines has a rule u v (u ≠ v, and no rule is repeated).
Output
The n tasks in order, separated by spaces; or cycle.
Constraints
1 ≤ n ≤ 100 and 0 ≤ m ≤ 1000, with no repeated rule.
Example
Input:
4 3
3 1
1 0
0 2
Output:
3 1 0 2
Why it works
A task with in-degree 0 waits for nothing, so it can safely go next. If none exists while tasks remain, those tasks wait on each other in a cycle.
Examples
4 3 3 1 1 0 0 2
3 1 0 2
3 3 0 1 1 2 2 0
cycle
Hints
Hint 1
Store the rules in a matrix edge[u][v] and count each task's in-degree.
Hint 2
n times: find the smallest task with in-degree 0 that is not done; if there is none, there is a cycle.
Hint 3
Print it, mark it done, and lower the in-degree of every task it points to.
Solution
Show one correct solution (try it yourself first)
#include <stdio.h>
int edge[100][100];
int main(void) {
int n, m;
scanf("%d %d", &n, &m);
int indegree[100] = {0}, done[100] = {0}, order[100];
for (int i = 0; i < m; i++) {
int u, v;
scanf("%d %d", &u, &v);
edge[u][v] = 1;
indegree[v]++;
}
for (int k = 0; k < n; k++) {
int u = -1;
for (int i = 0; i < n; i++) {
if (!done[i] && indegree[i] == 0) {
u = i;
break;
}
}
if (u == -1) {
printf("cycle\n");
return 0;
}
done[u] = 1;
order[k] = u;
for (int v = 0; v < n; v++)
if (edge[u][v]) indegree[v]--;
}
for (int k = 0; k < n; k++) {
if (k > 0) printf(" ");
printf("%d", order[k]);
}
printf("\n");
return 0;
}