Cod sursa(job #659421)

Utilizator XbyteAvram Florin Xbyte Data 10 ianuarie 2012 17:06:43
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include<fstream>
#include<cstdio>
#include<vector>

using namespace std;

#define pb push_back

const int MaxN = 50001;
const char InFile[] = "sortaret.in";
const char OutFile[] = "sortaret.out";

int N,M,lg,Q[MaxN],gre[MaxN];
vector<int> G[MaxN];

ifstream fin(InFile);
ofstream fout(OutFile);

void sortare()
{
	int i,nod;
	vector<int>::iterator it,iend;
	lg = 0;
	for( i = 1 ; i <= N ; i++ )
		if( !gre[i] )
			Q[++lg] = i;
	for( i = 1 ; i <= N ; i++ )
		{
			nod = Q[i];
			iend = G[nod].end();
			for( it = G[nod].begin() ; it < iend ; ++it )
				{
					gre[*it]--;
					if( !gre[*it] )
						Q[++lg] = *it;
				}
		}
}

int main()
{
	fin >> N >> M;
	int x,y,i;
	for( i = 0 ; i < M ; i++ )
		{
			fin >> x >> y;
			G[x].pb(y);
			gre[y]++;
		}
	fin.close();
	sortare();
	for( i = 1 ; i <= N ; i++ )
		fout << Q[i] << ' ';
	fout << '\n';
	fout.close();
	return 0;
}