How long will the project take? – Algorithms Practice

Tasks can run at the same time, unless one must wait for another. How soon can everything be finished?

What to build

A program that finds the earliest time the whole project can finish.

Requirements

Each task has a duration, and any number of tasks can run at the same time.
A task starts only when all the tasks it depends on have finished.
Print the time at which the last task finishes.
Print cycle if the rules cannot all be followed.

Input

The first line has n and m. The second line has the n durations. Each of the next m lines has a rule u v, which means u must finish before v starts.

Output

The earliest finish time of the project, or cycle.

Constraints

1 ≤ n ≤ 100, 0 ≤ m ≤ 1000, and each duration is from 1 to 1000.

Example

Input:

Output:

Why it works

Taking tasks in topological order means every prerequisite's finish time is known before it is needed. The final answer is the length of the longest chain of waiting, which project managers call the critical path.

Examples

Example 1 · Input

Expected output

Example 2 · Input

Expected output

cycle

Hints

Hint 1

Process the tasks in topological order, using Kahn's algorithm.

Hint 2

A task can start when the last of its prerequisites finishes, so keep the largest finish time among them.

Hint 3

If fewer than `n` tasks are processed, there is a cycle.

Solution

Show one correct solution (try it yourself first)

#include <stdio.h>

int edge[100][100];

int main(void) {
    int n, m, d[100], indegree[100] = {0}, start[100] = {0};
    int queue[100], front = 0, rear = 0;
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++) scanf("%d", &d[i]);
    for (int i = 0; i < m; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        edge[u][v] = 1;
        indegree[v]++;
    }
    for (int v = 0; v < n; v++)
        if (indegree[v] == 0) queue[rear++] = v;
    int done = 0, total = 0;
    while (front < rear) {
        int u = queue[front++];
        done++;
        int finish = start[u] + d[u];
        if (finish > total) total = finish;
        for (int v = 0; v < n; v++) {
            if (edge[u][v]) {
                if (finish > start[v]) start[v] = finish;
                if (--indegree[v] == 0) queue[rear++] = v;
            }
        }
    }
    if (done < n) printf("cycle\n");
    else printf("%d\n", total);
    return 0;
}

Lesson: Topological sort →