Cod sursa(job #1249600)

Utilizator bogdanpaunFMI Paun Bogdan Gabriel bogdanpaun Data 27 octombrie 2014 11:11:38
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include <iostream>
#include <cstdio>
using namespace std;

int n , i ,x , y,m;
struct node{
    int val;
    node *next;
};
node *G[50005],*tmp;
int deg[50050],st[50050];


int main()
{
    freopen("sortaret.in","r",stdin);
    freopen("sortaret.out","w",stdout);

    scanf("%d%d",&n,&m);
    for(i=1;i<=m;++i){
        scanf("%d %d",&x,&y);
        tmp = new node;
        tmp->val = y;
        tmp->next = G[x];
        G[x] = tmp;
        deg[y]++;
    }

    for(i=1;i<=n;++i)
        if( deg[i] == 0 ) st[ ++st[0] ] = i;

    for(i=1;i <=n;++i){
        tmp = G[ st[i] ];
        while( tmp ){
            deg[ tmp->val ]--;
            if( deg[ tmp->val ] == 0 ) st[ ++st[0] ] = tmp->val;
            tmp = tmp->next;
        }

    }
    for(i=1;i<=n;++i)
        printf("%d ",st[i]);

    return 0;
}