Cod sursa(job #1439280)

Utilizator adina0822Ciubotaru Adina-Maria adina0822 Data 22 mai 2015 00:15:03
Problema Sortare topologica Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
using namespace std;
#include <fstream>
FILE *f=fopen ("sortaret.in","r");
FILE *fout=fopen ("sortaret.out", "w");

int n,m,x,y,deg[50001],g[50001][100],q[50001];
void read();
void solve();
void write();

int main ()
{

    read();
    solve();
    write();

    return 0;
}

void read()
{
    fscanf(f,"%d%d",&n,&m);
    while(m--)
    {
        fscanf(f,"%d%d",&x,&y);
        g[x][++g[x][0]]=y;
        deg[y]++;
    }
}

void solve()
{
    int i,j,x;

    for(i=1; i<=n; i++)
    {
        if(!deg[i])
        {
            q[++q[0]]=i;
        }
    }
    for(i=1; i<=n; i++)
    {
        x=q[i];

        for(j=1; j<=g[x][0]; j++)
        {
            deg[g[x][j]]--;
            if(!deg[g[x][j]]) q[++q[0]]=g[x][j];

        }

    }
}

void write()
{
    int i;
    for(i=1; i<=q[0]; i++) fprintf(fout,"%d ",q[i]);
}