Cod sursa(job #1293365)

Utilizator turbowin120Amarandei-Stanescu Alexandru turbowin120 Data 15 decembrie 2014 20:08:11
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include <stdio.h>
using namespace std;

int vf[200001], nr=0, urm[200001], lst[200001],cnt=0;
bool viz[100011];
int tata[101337];
inline void adauga(int x, int y)
{
    ++nr;
    vf[nr]=y;
    urm[nr]=lst[x];
    lst[x]=nr;
}

void dfs(int x)
{
    viz[x]=true;
    int y,p;
    p=lst[x];
    while (p!=0)
    {
        y=vf[p];
        if(!viz[y]) dfs(y);
        p=urm[p];
    }
    tata[++cnt]=x;
}
int main()
{
    int n,m,x,y;
    FILE * in, *out;
    in=fopen ("sortaret.in","r");
    out=fopen ("sortaret.out","w");
    fscanf(in,"%d%d",&n,&m);

    for(int i=1;i<=m;i++)
    {
        fscanf(in,"%d%d",&x,&y);
        adauga(x,y);
    }


    for(int i=1;i<=n;i++)
    {
        if(viz[i]==0)
        {
            dfs(i);

        }
    }
    for(int i=n;i>=1;i--)
    fprintf(out,"%d ",tata[i]);

    return 0;
}