Cod sursa(job #1995763)

Utilizator horiacoolNedelcu Horia Alexandru horiacool Data 29 iunie 2017 02:50:06
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream f("sortaret.in");
ofstream g("sortaret.out");

int N,M;
bool viz[50003];
vector <int> v[50003];

void DF(int xp)
{
    int i=0,sol[50003];
    stack <int> S;
    bool ok;

    S.push(xp);
    sol[++i] = S.top();
    viz[xp] = true;

    while( S.empty() == false )
    {
        ok = false;

        for(int k = 0 ; k < v[S.top()].size() ; k++)
        {
            if( viz[ v[S.top()][k] ] == false )
            {
                ok = true;
                viz[ v[S.top()][k] ] = true;
                sol[++i] = v[S.top()][k];
                S.push(v[S.top()][k]);
                break;
            }
        }

        if( ok == false )
            S.pop();
    }

    for(i = 1 ; i <= N ; i++)
        g<<sol[i]<<' ';
}

int main()
{
    int x,y,rad;
    f>>N>>M;
    for(int i = 1 ; i <= M ; i++)
    {
        f>>x>>y;
        v[x].push_back(y);
        viz[y] = true;
    }
    for(int i = 1 ; i <= N ; i++)
    {
        if( viz[i] == false )
            rad = i;
        viz[i] = false;
    }
    DF(rad);
    return 0 ;
}