Cod sursa(job #1254185)

Utilizator andreiagAndrei Galusca andreiag Data 2 noiembrie 2014 12:12:03
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.65 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;
const int Nmax = 50055;

vector<int> G[Nmax];
int viz[Nmax], sol[Nmax];

void dfs(int v)
{
    for (auto x: G[v])
        if (!viz[x])
            dfs(x);

    viz[v] = 1;
    sol[++sol[0]] = v;
    return;
}

int main()
{
    ifstream f ("sortaret.in");
    ofstream g ("sortaret.out");

    int N, M, a, b;
    f >> N >> M;
    for (int i = 0; i < M; i++) {
        f >> a >> b;
        G[a].push_back(b);
    }
    
    for (int i = 1; i <= N; i++)
        if (!viz[i])
            dfs(i);
    
    for (int i = N; i > 0; i--)
        g << sol[i] << ' ';
    g << '\n';

    return 0;
}