Pagini recente » Cod sursa (job #1790845) | Cod sursa (job #1103876) | Cod sursa (job #2681243) | Cod sursa (job #1900682) | Cod sursa (job #206589)
Cod sursa(job #206589)
#include <stdio.h>
#include <stdlib.h>
int N,M;
int * A[50001];
bool vis[50001];
struct rec {int node; rec * next;} *fi, *la, *st, *dr;
void citire()
{
freopen("sortaret.in","r",stdin);
scanf("%d %d",&N,&M);
for(int i = 1 ; i <= N; ++i)
{
A[i] = (int*) malloc(sizeof(int));
A[i][0] = 0;
}
for(int i = 0 ; i < M; ++i)
{
int u,v;
scanf("%d %d",&u,&v);
A[u][0] ++;
A[u] = (int*) realloc(A[u], (A[u][0] + 1) * sizeof(int));
A[u][A[u][0]] = v;
}
}
void add(int key,rec * & l,rec * & r)
{
if(!l)
{
r = l = (rec*) malloc(sizeof (rec));
l->node = key;
l->next = 0;
}
else
{
r = r->next = (rec*) malloc(sizeof (rec));
r->node = key;
r->next = 0;
}
}
void dfs(int i)
{
vis[i] = 1;
add(i,st,dr);
for(int j = 1; j <= A[i][0]; ++j)
if(!vis[A[i][j]])
dfs(A[i][j]);
}
void tsort()
{
for(int i = 1; i <= N; ++i)
if(!vis[i])
{
dfs(i);
dr->next = fi;
fi = st;
if(!la) la = dr;
st = dr = 0;
}
freopen("sortaret.out","w",stdout);
for(rec * p = fi ; p != 0 ; p = p -> next)
printf("%d ",p->node);
}
int main()
{
citire();
tsort();
return 0;
}