Cod sursa(job #2135027)

Utilizator andrei.gramescuAndrei Gramescu andrei.gramescu Data 18 februarie 2018 15:40:13
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
#define NMAX 50005
vector<int> a[NMAX], sol;
int n, m, viz[NMAX];

void DFS(int nod){
    viz[nod] = 1;
    for(int i=0; i<a[nod].size(); i++){
        if(!viz[a[nod][i]]){
            DFS(a[nod][i]);
        }
    }
    sol.push_back(nod);
}

void TopSort(){
    for(int i=1; i<=n; i++){
        if(viz[i] == 0){
            DFS(i);
        }
    }
}

int main(){

    int x, y, i;
    freopen("sortaret.in", "r", stdin);
    freopen("sortaret.out", "w", stdout);

    scanf("%d%d", &n, &m);
    for(i=1; i<=m; i++){
        scanf("%d%d", &x, &y);
        a[x].push_back(y);
    }
    TopSort();
    reverse(sol.begin(), sol.end());
    for(i=0; i<sol.size(); i++){
        printf("%d ", sol[i]);
    }
    return 0;
}