Cod sursa(job #581141)

Utilizator cdascaluDascalu Cristian cdascalu Data 13 aprilie 2011 20:05:32
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
#include<fstream>
#include<queue>
#include<vector>
#include<bitset>
#define Nmax 50001
using namespace std;
int N,M,gr[Nmax];
vector<int> G[Nmax];
int Q[Nmax];
bitset<Nmax> inQ;
void df()
{
	int i,nod;
	for(i=1;i<=N;++i)
	{
		nod = Q[i];
		for(vector<int>::iterator it = G[nod].begin();it!=G[nod].end();++it)
		{
			--gr[*it];
			if(!gr[*it])Q[++Q[0]] = *it;
		}
	}	
}
int main()
{
	ifstream f("sortaret.in");
	f>>N>>M;
	int i,x,y;
	for(i=1;i<=M;++i)
	{
		f>>x>>y;
		G[x].push_back(y);
		++gr[y];
	}
	f.close();
	for(i=1;i<=N;++i)
		if(!gr[i])Q[++Q[0]] = i;
	df();
	ofstream g("sortaret.out");
	for(i=1;i<=N;++i)
		g<<Q[i]<<" ";
	g.close();
	return 0;
}