Pagini recente » Cod sursa (job #2693780) | Cod sursa (job #2053542) | Cod sursa (job #1226813) | Cod sursa (job #1994074) | Cod sursa (job #832983)
Cod sursa(job #832983)
#include <stdio.h>
#include <list>
#define MAXN 50000
int N,M,i;
std::list<int> startnodes;
std::list<int> neigh[MAXN];
bool hasincoming[MAXN];
bool visited[MAXN];
int sorted[MAXN];
int sorted_index = 0;
void DFS(int node)
{
sorted[sorted_index++] = node;
std::list<int>::iterator it;
for(it = neigh[node].begin(); it != neigh[node].end(); it++){
if(!visited[*it])
DFS(*it);
}
visited[node] = true;
}
int main(int argc, char* argv[])
{
freopen("sortaret.in","r",stdin);
freopen("sortaret.out","w",stdout);
scanf("%d %d",&N,&M);
for(i=0;i<M;i++){
int a,b;
scanf("%d %d",&a,&b);
neigh[a-1].push_front(b-1);
hasincoming[b-1] = true;
}
for(i=0;i<N;i++){
if( !hasincoming[i] )
startnodes.push_front(i);
}
std::list<int>::iterator it;
for(it = startnodes.begin(); it != startnodes.end(); it++){
DFS(*it);
}
for(i=0;i<N;i++)
printf("%d ",sorted[i]+1);
return 0;
}