Cod sursa(job #1846992)

Utilizator mateialexandru25Matei Alexandru mateialexandru25 Data 14 ianuarie 2017 11:04:27
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <stdio.h>
#include <stack>
#define nmax 50001
#define mmax 100001

using namespace std;
FILE *f=fopen("sortaret.in","r");
FILE *g=fopen("sortaret.out","w");

struct nod {int info; nod*urm;};
int n,m;
nod *prim[nmax];
int viz[nmax];
stack <int> S;


void add(nod*&prim,int x)
{ nod*p=new nod; p->info=x; p->urm=prim; prim=p;}

void Citire()
{ int i,x,y;
  fscanf(f,"%d%d",&n,&m);
  for(i=1;i<=m;i++)
  { fscanf(f,"%d%d",&x,&y);
    add(prim[x],y);
  }
}

void DFS(int x)
{ viz[x]=1;
  nod*p;
  for(p=prim[x];p;p=p->urm)
    if(viz[p->info]==0) DFS(p->info);
  S.push(x);
}

void SortareTopologica()
{ int i;
  for(i=1;i<=n;i++)
     if(viz[i]==0) DFS(i);
  while(!S.empty())
    { fprintf(g,"%d ",S.top());
      S.pop();
    }
}

int main()
{ Citire();
  SortareTopologica();
  return 0;
}