Cod sursa(job #1253407)

Utilizator robert.iacobIacob Robert robert.iacob Data 1 noiembrie 2014 11:26:36
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;
vector <int>L[50003];

int n, m;
int v[50003],timpfinal[50003],k;

void Citire()
{
    ifstream fin("sortaret.in");
    fin >> n >> m; //m-numarul de muchii; n-nr de noduri
    int i, x, y;
    for (i = 1; i <= m; i++)
    {
        fin >> x >> y;
        L[x].push_back(y);
    }
    fin.close();
}

void DFS_timp_final(int x)
{
    v[x] = 1;
    for (unsigned int i = 0; i < L[x].size(); i++)
        if (v[L[x][i]] == 0)
            DFS_timp_final(L[x][i]);
    timpfinal[++k]=x;
}

int main()
{
    Citire();
    for(int i=1;i<=n;i++)
    {
        if(!v[i])
            DFS_timp_final(i);
    }

    ofstream fout("sortaret.out");
    for (int i=n;i>0;i--)
        fout<<timpfinal[i]<<" ";
    fout<<"\n";
    fout.close();
    return 0;
}