Cod sursa(job #898153)

Utilizator botixMagyarosi Botond botix Data 28 februarie 2013 07:50:42
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
#include <iostream>
#include <fstream>
#define nMax 50001

bool viz[nMax] = {0};
int n, m, nr = 0;
int A[nMax][1000] = {0};
int list[nMax];

using namespace std;

void DFS(int x)
{
    viz[x] = true;
    list[nr++] = x;

    for(int i=1; i<=A[x][0]; i++)
    {
        if(!viz[A[x][i]])
            DFS(A[x][i]);
    }
}

int main()
{
    int x, y;
    fstream f, g;
    f.open("sortaret.in", ios::in);
    g.open("sortaret.out", ios::out);
    f >> n >> m;
    for(int i=1; i<=m; i++)
    {
        f >> x >> y;

        A[x][0]++;
        A[x][A[x][0]] = y;
    }

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

    for(int i=0; i<nr; i++)
        g << list[i] << ' ';
}