Cod sursa(job #802219)

Utilizator Theorytheo .c Theory Data 26 octombrie 2012 00:02:53
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include<fstream>
#include<vector>
#define nmax 50009

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

vector <int> v;
int N, M;
vector <int> G[nmax];
bool o[nmax];
void read()
{
    fin >>N>>M;
    for(int i = 1; i <= M; i++)
    {
        int x, y;
        fin >>x >>y;
        G[x].push_back(y);
    }
}
void DF(int x)
{
    o[x] = true;
    for(int i = 0 ; i < G[x].size() ; i++)
    {
        if(o[G[x][i]] == false)
        {
            o[G[x][i]] = true;
            DF(G[x][i]);

        }
    }
    v.push_back(x);
}


void sortare_topologica()
{
    for(int i = 1; i <= N ;i++)
    if(o[i] == false)
        DF(i);
}

void afisare()
{
    for(int i = v.size() - 1; i >= 0 ;i--)
        fout << v[i] <<" ";

}
int main()
{
    read();
    fin.close();
    sortare_topologica();
    afisare();


    return 0;
}