Cod sursa(job #861179)

Utilizator galbenugalbenu dorin galbenu Data 21 ianuarie 2013 09:16:00
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include<iostream>
#include<fstream>
#include<cstdio>
#define nmax 50050
#define mmax 100050
using namespace std;
FILE *f=fopen("sortaret.in","r"),*g=fopen("sortaret.out","w");
struct nod
{
    unsigned short int inf;
    nod *urm;
};
nod *L[nmax];
unsigned short int sol[nmax],n;
unsigned int m,i;
bool viz[nmax];
void add(unsigned int x,unsigned int y)
{
    nod *nou;
    nou=new nod;
    nou->inf=x;
    nou->urm=L[y];
    L[y]=nou;
}
 
void read()
{   unsigned short int x,y;
    fscanf(f,"%hd %u",&n,&m);
    for(unsigned int i=1;i<=m;i++)
    fscanf(f,"%hd %hd",&x,&y),add(x,y);
}
void DF(int x)
{
    nod *p;
    viz[x]=1;
    for(p=L[x];p;p=p->urm)
    if(!viz[p->inf])
    DF(p->inf);
    sol[++sol[0]]=x;
}
void solve()
{
    for(unsigned int i=1;i<=n;i++)
    if(!viz[i])
    DF(i);
}
void show()
{
    for(unsigned int i=1;i<=sol[0];i++)
    fprintf(g,"%u ",sol[i]);
}
int main()
{
    read();
    solve();
    show();
    fclose(f);
    fclose(g);
    return 0;
}