Cod sursa(job #1026504)

Utilizator tudy23Coder Coder tudy23 Data 11 noiembrie 2013 18:18:07
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include <fstream>
#include <vector>

using namespace std;

const int ct = 50002;

vector< vector<int> > much;
vector<int> sol;
int marc[ct];
int n,m;
int a,b;

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

void citire()
{
    f>>n>>m;
    much.resize(n+1);
    for(int i=0;i<m;++i)
    {
        f>>a>>b;
        much[a].push_back(b);
    }
    f.close();
}

void visit(int n)
{
    if(marc[n]==1)
        return;
    else if(marc[n] == 0)
    {
        for(unsigned int i=0;i<much[n].size();++i)
            visit(much[n][i]);
        marc[n] = 2;
        sol.push_back(n);
    }
}

void solve()
{
    for(int i=1;i<=n;++i)
    {
        if(marc[i]==0)
        visit(i);
    }
    for(int i=n-1;i>=0;--i)
        h<<sol[i]<<" ";
}
int main()
{
    citire();
    solve();
    return 0;
}