Cod sursa(job #546674)

Utilizator DanceKrissCristian Oancea DanceKriss Data 5 martie 2011 12:45:57
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb
#include <iostream>
#include<stdio.h>
#include<fstream>

using namespace std;
const int CATE = int(5e4) + 2;
int c[CATE], grad[CATE],
    n,m;
typedef struct nod
    {
        int inf;
        nod *next;
    } TNOD;
TNOD *v[CATE];

void add( int a, int b )
{
    TNOD *p = new TNOD;
    p->inf = a;
    p->next = v[b];
    v[b] = p;
}

void citire()
{
    int i,x,y;
    ifstream in("sortaret.in");
    in>>n>>m;
    for( i=1; i<=m; i++ )
        {
            in>>x>>y;
            add( y, x );
            grad[y]++;
        }
}

void toposort()
{
    int i,it=0;

    for( i=1; i<=n; i++ )
       if( !grad[i] ) c[it++] = i;

    for( i=0; i<n; i++ )
    {
        int x=c[i];
        for( TNOD *p=v[x]; p; p=p->next )
            {
                grad[p->inf]--;
                if( !grad[p->inf] ) c[it++] = p->inf;
            }
    }
}

void afish()
{
    int i=0;
    while(i<n) printf("%d ",c[i++]);
    cout<<endl;
}

int main()
{
    freopen("sortaret.out","w",stdout);
    citire();
    toposort();
    afish();
    fclose(stdout);
    return 0;
}