Pagini recente » Cod sursa (job #458073) | Cod sursa (job #2690589) | Cod sursa (job #2949859) | Cod sursa (job #2605596) | Cod sursa (job #160421)
Cod sursa(job #160421)
//Sortare topologica
#include <stdio.h>
#define INPUT "sortaret.in"
#define OUTPUT "sortaret.out"
#define NMAX 50001
#define MMAX 100001
int N, M;
int viz[NMAX], q[NMAX];
int t;
struct nod
{
nod* leg;
int vec;
}*graf[NMAX];
void afis()
{
int i;
for(i = N; i>1; --i)
printf("%d ", q[i]);
printf("%d\n", q[1]);
}
void DF(int src)
{
viz[src] = 1;
nod* l;
for(l = graf[src]; l; l = l->leg)
if(!viz[l->vec])
DF(l->vec);
viz[src] = ++t;
}
void solve()
{
int i;
for(i = 1; i <= N; ++i)
if(!viz[i])
DF(i);
for(i = 1; i <= N; ++i)
q[viz[i]] = i;
}
void citire()
{
scanf("%d %d", &N, &M);
int i;
for(i = 1; i <= M; ++i)
{
int a, b;
scanf("%d %d", &a, &b);
nod *l = new nod;
l -> vec = b;
l -> leg = graf[a];
graf[a] = l;
}
}
int main()
{
freopen(INPUT, "r", stdin);
freopen(OUTPUT, "w", stdout);
citire();
solve();
afis();
return 0;
}