Cod sursa(job #2945389)

Utilizator SerbanCaroleSerban Carole SerbanCarole Data 23 noiembrie 2022 19:05:30
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.8 kb
#include <iostream>
#include <vector>
#include <bitset>
using namespace std;

//ifstream cin("sortaret.in");
//ofstream cout("sortaret.out");

const int NMAX = 5e4+1;

int n , m , x , y, topo[NMAX], k;

vector <int> g[NMAX];

bitset <NMAX> b;

void dfs(int x){
    int l = g[x].size();
    for(int i = 0 ; i < l ; i++){
        int val = g[x][i];
        if(!b[val]){
            b[val] = 1;
            dfs(val);
        }
    }
    topo[k--] = x;
}

int main()
{
    cin >> n >> m;

    k = n;

    while(m--){
        cin >> x >> y;
        g[x].push_back(y);
    }

    for(int i = 1; i <= n ; i++){
        if(!b[i]){
            b[i] = 1;
            dfs(i);
        }
    }

    for(int i = 1; i <= n ; i++){
        cout << topo[i] << ' ';
    }

    return 0;
}