Cod sursa(job #1494531)

Utilizator andi12Draghici Andrei andi12 Data 1 octombrie 2015 12:38:00
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include <cstdio>

using namespace std;
const int N=50001;
const int M=100001;
int vf[M];
int lst[N];
int urm[M];
int c[N];
int pred[N];
int p,st=1,dr;
void ad(int x,int y)
{
    p++;
    vf[p]=y;
    urm[p]=lst[x];
    lst[x]=p;
}
void bfs(int x)
{
    int poz;
    if(st>dr)
        return ;
    else
    {
        poz=lst[x];
        while(poz!=0)
        {
            pred[vf[poz]]--;
            if(pred[vf[poz]]==0)
            {
                dr++;
                c[dr]=vf[poz];
            }
            poz=urm[poz];
        }
        st++;
        bfs(c[st]);
    }
}
int main()
{
    FILE *in,*out;
    in=fopen("sortaret.in","r");
    out=fopen("sortaret.out","w");
    int n,m,i,x,y,ok=0;
    fscanf(in,"%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        fscanf(in,"%d%d",&x,&y);
        ad(x,y);
        pred[y]++;
    }
    for(i=1;i<=n;i++)
    {
        if(pred[i]==0 && ok==0)
        {
            ok=1;
            x=i;
        }
        if(pred[i]==0)
        {
            dr++;
            c[dr]=i;
        }
    }
    bfs(x);
    for(i=1;i<=n;i++)
        fprintf(out,"%d ",c[i]);
    return 0;
}