Challenge: Course Order

Lab C++ Intermediate 20 points

There are n courses (0 … n − 1) and rules a b (“a before b”). Print an order using Kahn's algorithm, always taking the smallest-numbered ready course (use a min-heap), or impossible.

Input

Line 1: n m. Then m lines a b.

Output

The order, or impossible.

Example

Input

Output

2 3 1 0

Sample input available Sample output available

Editor

C++

Hints

indeg[b]++ for every rule a b.

Use a min-heap for the ready courses.

Fewer than n in the order means a cycle.

Solution explanation

The heap makes the answer unique: the smallest ready course always goes next.

Show solution

#include <functional>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> after(n);
    vector<int> indeg(n, 0);
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        after[a].push_back(b);
        indeg[b]++;
    }
    priority_queue<int, vector<int>, greater<int>> ready;
    for (int v = 0; v < n; v++)
        if (indeg[v] == 0) ready.push(v);
    vector<int> order;
    while (!ready.empty()) {
        int v = ready.top();
        ready.pop();
        order.push_back(v);
        for (int w : after[v])
            if (--indeg[w] == 0) ready.push(w);
    }
    if ((int)order.size() < n) {
        cout << "impossible" << endl;
        return 0;
    }
    for (int i = 0; i < n; i++) cout << order[i] << (i + 1 < n ? " " : "\n");
    return 0;
}

Output

Answer