Cod sursa(job #158077)

Utilizator QbyxEros Lorand Qbyx Data 13 martie 2008 13:56:40
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include <stdio.h>
#define nmax 100001

struct NOD{int nod; NOD *next;};

NOD *g[nmax];

int i, n, m, x, y, ok[nmax], r[nmax], k;

void dfs(int nod)
{
   ok[nod] = 1;

   r[++k] = nod;

   NOD *p = g[nod];
   while (p)
   {
       if (!ok[p->nod]) dfs(p->nod);
       p = p->next;
   }
}

int main()
{
    int ok2[nmax];

    freopen("sortaret.in", "rt", stdin);
    freopen("sortaret.out", "wt", stdout);

    scanf("%d %d", &n, &m);

    for (i = 1; i <= m; ++i)
    {
	scanf("%d %d", &x, &y);

	NOD *p = new NOD;

	p->nod = y;
	p->next = g[x];
	g[x] = p;

	ok2[y] = 1;
    }

    for (i = 1; i <= n; ++i)
	if(!ok2[i])
	    dfs(i);

    for (i = k; i >= 1; --i)
	printf("%d ", r[i]);

    return(0);
}