Cod sursa(job #556504)

Utilizator mihaionlyMihai Jiplea mihaionly Data 16 martie 2011 10:19:51
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
#include <cstdio>
using namespace std;
FILE *fin=fopen("sortaret.in","r");
FILE *fout=fopen("sortaret.out","w");
#define nmax 50001
int n,m,po[nmax],nr;
bool viz[nmax];
struct graf {
graf *urm;
int x;
} *G[nmax];
void dfs(int nod)
 {
 viz[nod]=true;
 for(graf *g=G[nod];g!=NULL;g=g->urm)
  {
  if(!viz[g->x])
   dfs(g->x);
  }
 po[++nr]=nod;
 }
void add(graf *&g,int x)
 {
 graf *p=new graf;
 p->x=x;
 p->urm=g;
 g=p;
 }
int main()
 {
 fscanf(fin,"%d %d",&n,&m);
 int x,y,i;
 for(i=1;i<=m;i++)
  {
  fscanf(fin,"%d %d",&x,&y);
  add(G[x],y);
  }
 for(i=1;i<=n;i++)
  if(!viz[i])
   dfs(i);
 for(i=n;i>=1;i--)
  fprintf(fout,"%d ",po[i]);
 return 0;
 }