Cod sursa(job #1984491)

Utilizator ioan32Ioan Eftenoiu ioan32 Data 24 mai 2017 23:36:28
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("sortaret.in");
ofstream g("sortaret.out");
int t[2][100001], start[100001], N, M, viz[100001], sol[100001];
int nrsol;


void DFS(int nod)
{


    cout<<nod<<" ";

    int man = start[nod];

    viz[nod] = 1;

    while(man)
    {
        if(viz[t[0][man]] == 0)
            DFS(t[0][man]);
        man = t[1][man];
    }

    sol[++nrsol] = nod;

}

void rezolvare()
{

   for(int i = 1; i <= N; i++)
        if(!viz[i])
          DFS(i);

    for(int i = N; i >= 1; i--)
         g<<sol[i]<<" ";

}

int main()
{int i, j, k = 0, x, y;

    f>>N >>M;

    for(i = 1; i <= M; i++){

        f>>x >>y;

        k ++;
        t[0][k] = y;
        t[1][k] = start[x];
        start[x] = k;
    }

    rezolvare();


    return 0;
}