Cod sursa(job #145880)

Utilizator moga_florianFlorian MOGA moga_florian Data 29 februarie 2008 17:25:36
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include<stdio.h>
#define Nmax 50005

int *vec[Nmax];
int Nvec[Nmax], gint[Nmax];
int Q[Nmax];
int NQ=0;

int main(){

    FILE *fin = fopen("sortaret.in","r");
    int N,M;
    fscanf(fin,"%d%d",&N,&M);
    
    for(int i=1;i<=M;i++){
        int x,y;
        fscanf(fin,"%d%d",&x,&y);
        Nvec[x]++;
    }
    
    fclose(fin);
    
    for(int i=1;i<=N;i++){
        vec[i] = new int[Nvec[i] + 3];
        Nvec[i] = 0;
    }
    
    fin = fopen("sortaret.in","r");
    fscanf(fin,"%d%d",&N,&M);

    for(int i=1;i<=M;i++){
        int x,y;
        fscanf(fin,"%d%d",&x,&y);
        vec[x][++Nvec[x]] = y;
        gint[y] ++;
    }
    
    for(int i=1;i<=N;i++)
        if(gint[i] == 0)
            Q[++NQ] = i;
    
    for(int i=1;i<=N;i++)
        for(int j=1;j<=Nvec[Q[i]];j++){
            gint[vec[Q[i]][j]] --;
            if(gint[vec[Q[i]][j]] == 0)
                Q[++NQ] = vec[Q[i]][j];
        }

    FILE *fout = fopen("sortaret.out","w");

    for(int i=1;i<=N;i++)
        fprintf(fout,"%d ",Q[i]);
    
    fclose(fout);
    fclose(fin);
    return 0;

}