Cod sursa(job #569259)

Utilizator chibicitiberiuChibici Tiberiu chibicitiberiu Data 1 aprilie 2011 11:01:37
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
#include<fstream>
#include<vector>
#include<queue>
using namespace std;

vector<int> lista[50005];
int NrVf;
queue<int> brr;
int Vizited[50005];
int apel;

void DFS(int node)
{
    Vizited[node] = ++apel;
    brr.push(node);

    for (int i=0; i<lista[node].size(); i++)
        if (!Vizited[lista[node][i]]) DFS(lista[node][i]);
}

int main()
{
    ifstream in ("sortaret.in");
    ofstream out ("sortaret.out");

    int NrM;
    in>>NrVf>>NrM;

    for (int x,y; NrM>0; NrM--)
    {
        in>>x>>y;
        lista[x].push_back(y);
    }

    for (int i=1; i<=NrVf; i++)
        if (!Vizited[i]) DFS(i);

    for (; !brr.empty(); brr.pop())
        out<<brr.front()<<" ";

    in.close();
    out.close();
    return 0;
}