Cod sursa(job #316828)

Utilizator ssergiussSergiu-Ioan Ungur ssergiuss Data 21 mai 2009 11:26:13
Problema Sortare topologica Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
# include <algorithm>
using namespace std;

# define DIM 1 << 10

struct graf {

    int nod;
    graf *urm;
};

int n, m, c[ DIM ], grad[ DIM ];
graf *lst[ DIM ];

void add ( int x, int y ) {

    graf *p = new graf;

    p->nod = y;
    p->urm = lst[ x ];
    lst[ x ] = p;
}

void read () {

	int i, x, y;

    scanf ( "%d%d", &n, &m );
    for ( i = 0; i < m; ++ i ) {

        scanf ( "%d%d", &x, &y );
        ++ grad[ y ];
		add ( x, y );
	}
}

void solve () {
    
    int i, st, dr;
    graf *p;

	dr = -1;
	for ( i = 1; i <= n; ++ i )
		if ( !grad[ i ] )
			c[ ++ dr ] = i;
	for ( st = 0; st <= dr; ++ st ) {

        printf ( "%d ", c[ st ] );

		for ( p = lst[ c[ st ] ]; p; p = p->urm ) {

			-- grad[ p->nod ];
			if ( !grad[ p->nod ] )
				c[ ++ dr ] = p->nod;
		}
	}
}

int main () {

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

    read ();
    solve ();

    return 0;
}