Cod sursa(job #363739)

Utilizator andreitheo87Teodorescu Andrei-Marius andreitheo87 Data 14 noiembrie 2009 16:12:45
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include<fstream>
#include<iostream>
#include<queue>
using  namespace std;
struct node{
    int vec;
    node* next;
};
node* vec[50000];
int n,m;
int main()
{
	freopen("sortaret.in", "r", stdin);
    freopen("sortaret.out", "w", stdout);
	scanf("%d %d",&n,&m);
	int gr[n];
	memset(vec,0,sizeof(vec));
	memset(gr,0,sizeof(gr));
	for(int i=0; i<m; i++)
	{
		int x,y;
		scanf("%d %d",&x,&y);
		x--; y--;
		node* nod = new node;
		nod->vec = y;
		nod->next = vec[x];
		vec[x] = nod;
		gr[y]++;
	}
	queue<int> q;
	for(int i=0; i<n; i++)
        if( gr[i] == 0 ) q.push(i);
    while( q.size() )
    {

        int next = q.front();
        q.pop();
        printf("%d ",next+1);
        node* p = vec[next];
        while( p ){
                gr[p->vec]--;
                if( gr[p->vec] == 0 ) q.push(p->vec);
                p = p->next;
        }
    }
    printf("\n");
	return 0;
}