Cod sursa(job #1644912)

Utilizator vladttturcuman vlad vladtt Data 10 martie 2016 10:15:48
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include <iostream>
#include <fstream>
#include <vector>

#define NMax 50010

using namespace std;

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


vector<int> v[NMax];
vector<int> rv[NMax];

int n,m,nr;

int CanGo[NMax];
int over[NMax];
int _list[NMax];



void dfs(int nod)
{
    bool ok =1;
    for(int i=0;i<rv[nod].size();i++)
        if(!over[rv[nod][i]])
        {
            ok=0;
            break;
        }
    if(ok)
    {
        over[nod]=1;
        _list[++nr]=nod;
    }

    for(int i=0;i<v[nod].size();i++)
        dfs(v[nod][i]);

}

int main()
{
    int a,b;

    fin>>n>>m;

    for(int i=1;i<=m;i++)
    {
        fin>>a>>b;

        v[a].push_back(b);
        rv[b].push_back(a);

        CanGo[b]=-1;
    }


    for(int i=1;i<=m;i++)
        if(CanGo[i]==0)
            dfs(i);


    for(int i=1;i<=n;i++)
        fout<<_list[i]<<' ';

    return 0;
}