Cod sursa(job #442813)

Utilizator szocsbarniSzocs Barna szocsbarni Data 15 aprilie 2010 13:07:01
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
#include <stdio.h>
#include <vector>
#define nmax 50001
using namespace std;
int n,m,pre[nmax],nr,viz[nmax];
vector<int> g[nmax];


void df (int x)
{
    viz [x] = 1;
    for (int i = 0; i < g[x].size (); i++)
        if (!viz[g[x][i]])
            df(g[x][i]);
    pre[++nr] = x;
}
int main ()
{
    freopen("sortaret.in","r",stdin);
    freopen("sortaret.out","w",stdout);
	int x,y;
    scanf("%d%d",&n,&m);
    for (int i = 1; i<=m; i++)
    {
        scanf("%d%d",&x,&y);
        g[x].push_back(y);
    }
    for (int i = 1; i <=n; i++)
        if (!viz[i])
            df(i);
    for (int i = n; i>0; i--)
        printf("%d ",pre[i]);
	printf("\n");
    return 0;
}