Cod sursa(job #1620343)

Utilizator LolkekzorChiorean Tudor Lolkekzor Data 29 februarie 2016 08:07:46
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include <fstream>
#include <list>
using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");

int n, m, x, y, i;
bool isVisit[50010];
list<int> graf[50010], topoSort;

void doTopoSort(int nod) {
    isVisit[nod] = true;
    for (list<int>::iterator it = graf[nod].begin() ; it != graf[nod].end() ; it++)
        if (!isVisit[*it])
            doTopoSort(*it);

    topoSort.push_front(nod);
}

int main()
{
    fin>>n>>m;
    for (i = 1 ; i <= m ; i++) {
        fin>>x>>y;
        graf[x].push_back(y);
    }

    for (i = 1 ; i <= n ; i++)
        if (!isVisit[i])
            doTopoSort(i);

    for (list<int>::iterator it = topoSort.begin() ; it != topoSort.end() ; it++)
        fout<<*it<<' ';

    return 0;
}