Cod sursa(job #1572265)

Utilizator cristinamateiCristina Matei cristinamatei Data 18 ianuarie 2016 20:27:19
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include <iostream>
#include <fstream>

using namespace std;

ifstream in("sortaret.in");
ofstream out("sortaret.out");

const int N = 50003;
const int M = 100003;
int n, m, nr, nri, vf[M], urm[M], lst[N], viz[N], stop[N];

void adauga( int x, int y )
{
    nr++;
    vf[nr] = y;
    urm[nr] = lst[x];
    lst[x] = nr;
}

void dfs( int x )
{
    viz[x] = true;
    int poz = lst[x], y;
    while ( poz != 0 )
    {
        y = vf[poz];
        if ( !viz[y] )
            dfs(y);
        poz = urm[poz];
    }
    stop[++nri] = x;
}

int main()
{
    int x, y;
    in >> n >> m;
    for ( int i = 1; i <= n; i++ )
    {
        in >> x >> y;
        adauga(x, y);
    }
    for ( int i = 1; i <= n; i++ )
        if ( viz[i] == false )
            dfs(i);
    for ( int i = n; i >= 1; i-- )
        out << stop[i]<<' ';
    return 0;
}