Topological sort

Go to the Jutge statement of the problem

We must perform n tasks, one at a time. Furthermore, some tasks must be done before others: there are m precedence relations between tasks. Write a program to print a way to sort the n tasks satisfying the m given precedences.

Input: Input consists of several cases. Every case begins with n, followed by m, followed by m ‍distinct pairs x y that indicate that task x must be done before task y. You can assume 1 \leq n \leq 10^4, 0 \leq m \leq 10n, and that the tasks are numbered from 0 to n − 1.

Output: For every case, print the lexicographically smallest order of the n tasks that fulfills the m ‍given precedences. There will always be, at least, one solution.

Hint

This problem is related to Problem 5.12 you will see in Problem class P6.

A possible C++ code to start the problem

// Topological sort
#include<iostream>
#include<vector>
#include<queue>

using namespace std;
using graph = vector<vector<int>>;
using VI = vector<int>;

VI compute_ordering(const graph& g, VI& indegree){
   // suggestion: use a priority_queue
}

void write(const VI& v){
    cout << v[0];
    for (size_t i = 1; i < v.size(); ++i)
        cout  << ' ' << v[i];
    cout << endl;
}

int main(){
    int n, m;
    while(cin >> n >> m){
        graph g(n);
        VI indegree(n, 0);
        for (int i = 0; i < m; ++i){
            int u, v;
            cin >> u >> v;
            g[u].push_back(v);
            ++indegree[v];//why could be useful to remember the in-degree of vertices?
        }
    VI ord = compute_ordering(g,indegree);
    write(ord);
    }
}

A possible solution

// Topological sort
#include<iostream>
#include<vector>
#include<queue>

using namespace std;
using graph = vector<vector<int>>;
using VI = vector<int>;

VI compute_ordering(const graph& g, VI& indegree){
    int n = g.size();
    priority_queue<int, vector<int>, greater<int>> pq;
    for (int u = 0; u < n; ++u){
        if (indegree[u]==0) pq.push(u);
    }
    VI ord;
    while(not pq.empty()){
        int u = pq.top();
        pq.pop();
        ord.push_back(u);
        for (size_t k = 0; k < g[u].size(); ++k){
            int v = g[u][k];
            --indegree[v];
            if (indegree[v]==0) pq.push(v);
        }
    }
    return ord;
}

void write(const VI& v){
    cout << v[0];
    for (size_t i = 1; i < v.size(); ++i)
        cout  << ' ' << v[i];
    cout << endl;
}

int main(){
    int n, m;
    while(cin >> n >> m){
        graph g(n);
        VI indegree(n, 0);
        for (int i = 0; i < m; ++i){
            int u, v;
            cin >> u >> v;
            g[u].push_back(v);
            ++indegree[v];
        }
    VI ord = compute_ordering(g,indegree);
    write(ord);
    }
}

Other Links