Cod sursa(job #145172)

Utilizator marinMari n marin Data 28 februarie 2008 15:53:14
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include <stdio.h>
#define DIM 50001

struct nod {
  int inf;
  nod *urm;
};


int i,j,nr,n,m,x,y;

int v[DIM],t[DIM];
nod *p[DIM];
int s[DIM];
nod *q;

void parc(int k){
  nod *q;
  v[k]=1;
  q=p[k];
  while (q!=NULL) {
    if (v[q->inf]!=1)
      parc(q->inf);
    q=q->urm;
  }
  s[++nr] = k;
}


int main(){
  FILE *f = fopen("sortaret.in","r");
  fscanf(f,"%d %d",&n,&m);
  for (i=1;i<=n;i++)
    p[i]=NULL;
  for (i=1;i<=m;i++) {
    fscanf(f,"%d %d",&x,&y);
    t[y]=1;
    q = new nod;
    q->inf = y;
    q->urm=p[x];
    p[x]=q;

/*    q = new nod;
    q->inf = x;
    q->urm=p[y];
    p[y]=q;*/
  }
  nr=0;
  for (i=1;i<=n;i++)
    if (t[i]==0)
      parc(i);
  FILE *g = fopen("sortaret.out","w");
  for (i=nr;i>=1;i--)
    fprintf(g,"%d ",s[i]);
  fclose(g);
  return 0;
}