Cod sursa(job #1037898)

Utilizator dragosaioaneiAioanei Dragos dragosaioanei Data 20 noiembrie 2013 20:48:15
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;
#define IN "sortaret.in"
#define OUT "sortaret.out"
#define NMAX 50005

int n,m;
vector<int> graf[NMAX];
int coada[NMAX];
int grad[NMAX];

int main()
{
    FILE * fin=fopen(IN,"r");
    FILE * fout=fopen(OUT,"w");

    int x,y,i,k,j;
    fscanf(fin,"%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        fscanf(fin,"%d%d",&x,&y);
        graf[x].push_back(y);
        grad[y]++;
    }

    k=0;
    for(i=1;i<=n;i++)
        if(grad[i]==0)
            coada[++k]=i;
    for(i=1;i<=n;i++)
    {
        x=coada[i];
        for(j=0;j<graf[x].size();j++)
        {
            grad[graf[x][j]]--;
            if(grad[graf[x][j]]==0)
                coada[++k]=graf[x][j];
        }
    }

    fprintf(fout,"%d",coada[1]);
    for(i=2;i<=n;i++)
        fprintf(fout," %d",coada[i]);
    fprintf(fout,"\n");

    fclose(fin);
    fclose(fout);
    return 0;
}