Cod sursa(job #1654971)

Utilizator Paul_StefanescuStefanescu Paul Mihnea Paul_Stefanescu Data 17 martie 2016 17:17:15
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include <iostream>
#include <cstdio>
#define NMAX 50005
#define MMAX 100005
using namespace std;
FILE *in,*out;
int vf[MMAX],urm[MMAX],lst[NMAX],v[NMAX],nr,n,m;
bool viz[NMAX];
void adauga(int x,int y)
{
    nr++;
    vf[nr]=y;
    urm[nr]=lst[x];
    lst[x]=nr;
}
void sorttop_invers(int x)
{
    viz[x]=true;
    int p,y;
    p=lst[x];
    while(p!=0)
    {
        y=vf[p];
        if(!viz[y])
            sorttop_invers(y);
        p=urm[p];
    }
    v[++nr]=x;
}
int main()
{
    in=fopen("sortaret.in","r");
    out=fopen("sortaret.out","w");
    int i,j;
    fscanf(in,"%d %d ", &n, &m);
    for(; m>0; m--)
    {
        fscanf(in,"%d%d", &i, &j);
        adauga(i,j);
    }
    nr=0;
    for(i=1;i<=n;i++)
        if(!viz[i])
            sorttop_invers(i);
    for(i=n;i>=1;i--)
        fprintf(out,"%d ",v[i]);
    return 0;
}