Topological orderings

Go to the Jutge statement of the problem

There are n tasks, which have to be done one by one. Some tasks must be done before others: there are m precedence relations between tasks. Write a program that prints all possible ways to order the n tasks according to the m given precedences.

Input: Input consists of a natural number n \geq 1, followed by a natural number m, followed by m ‍different pairs x, y, indicating that task x must be done before task y. Suppose that the tasks are numbered from 0 to n − 1.

Output: Print, one per line and in lexicographic order, all the ways of sorting the n tasks according to the m given precedences. There will always be at least one solution.

Hint

Revise how we solved Topological Sort in the lab L3.

A possible C++ code to start the problem

//Topological orderings

#include<iostream>
#include<vector>
#include<set>

using namespace std;

using VVI = vector<vector<int>>;
using VI = vector<int>;
using VB = vector<bool>;
using SI = set<int>;

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

void top_sorts(int k, const VVI& g, VI& sol, VB& mkd, VI& indegree, SI& deg_zero_vertices){
    // sorting function
}

int main(){
    int n, m;
    cin >> n >> m;
    VVI 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];
    }
    SI deg_zero_vertices;
    for (int v = 0; v < n; ++v)
        if (indegree[v] == 0)
            deg_zero_vertices.insert(v);
    VI sol(n);
    VB mkd(n, false);
    top_sorts(0, g, sol, mkd, indegree, deg_zero_vertices);
}

A possible solution

// Topological orderings

#include<iostream>
#include<vector>
#include<set>

using namespace std;

using VVI = vector<vector<int>>;
using VI = vector<int>;
using VB = vector<bool>;
using SI = set<int>;

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

void top_sorts(int k, const VVI& g, VI& sol, VB& mkd, VI& indegree, SI& deg_zero_vertices){
    int n = sol.size();
    if (k == n) 
        write(sol);
    else{
        SI tmp = deg_zero_vertices;
        for (int x : tmp){
            if (not mkd[x]){
                mkd[x] = true;
                sol[k] = x;
                deg_zero_vertices.erase(x);
                for (int y : g[x]){
                    --indegree[y];
                    if (indegree[y] == 0) deg_zero_vertices.insert(y);
                }
                top_sorts(k+1, g, sol, mkd, indegree, deg_zero_vertices);
                mkd[x] = false;
                for (int y : g[x]){
                    if (indegree[y] == 0) deg_zero_vertices.erase(y);
                    ++indegree[y];
                }
                deg_zero_vertices.insert(x);
            }
        }  
    }
}

int main(){
    int n, m;
    cin >> n >> m;
    VVI 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];
    }
    SI deg_zero_vertices;
    for (int v = 0; v < n; ++v)
        if (indegree[v] == 0)
            deg_zero_vertices.insert(v);
    VI sol(n);
    VB mkd(n, false);
    top_sorts(0, g, sol, mkd, indegree, deg_zero_vertices);
}