Cod sursa(job #1003688)

Utilizator valiro21Valentin Rosca valiro21 Data 1 octombrie 2013 12:32:59
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
#include <cstdio>
#include <vector>
#include <queue>

//defines
#define NMax 100001
#define scan scanf  //read
#define For(i,a,b) for(long i=a;i<=b;i++)

using namespace std;

//stl defines
#define V vector<long>
#define pb push_back
#define Q queue<long>
#define IFor(i,a) for(V::iterator i=a.begin(); i<a.end();i++)

//variables
V v[NMax];
long n,m,x,y,viz[NMax];
Q q;

//rapid defines
#define viz(i) viz[i]++
#define nviz(i) viz[i]--

//topologic sort
void topsort() {  
	long now;
	
	while(!q.empty()) {
		now=q.front();  //get front element
		printf("%ld ",now);
		IFor(i,v[now]) {
			nviz(*i);
			if(!viz[*i])  //test if the vertex became a primary vertex
				q.push(*i);  //add new element
		}
		q.pop();  //erase front(current) element
	}
}


//main
int main()
{
    freopen("sortaret.in","rt",stdin);
    freopen("sortaret.out","wt",stdout);
    
    scan("%ld %ld",&n,&m);
    For(i,1,m)
		scanf("%ld %ld",&x,&y),  //scan edge
		v[x].pb(y),
		viz(y);  //increase nr. of vertices adjacent with y(oriented graph)
	
	For(i,1,n)
		if(!viz[i])
			q.push(i);  //add to queue primary vertex(no adjacent vertices)
			
	topsort();
	
    return 0;
}