Cod sursa(job #697040)

Utilizator avram_florinavram florin constantin avram_florin Data 28 februarie 2012 21:47:59
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include<fstream>
#include<cstdio>
#include<vector>

using namespace std;

const int MaxN = 50001;

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

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

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

int main()
{
	ifstream fin( InFile );
	ofstream fout( OutFile );
	fin >> N >> M;
	int i,x,y;
	for( i = 0 ; i < M ; ++i )
		{
			fin >> x >> y;
			G[x].push_back(y);
			gri[y]++;
		}
	lg = 0;
	sortare();
	for( i = 1 ; i <= N ; i++ )
		fout << Q[i] << ' ';
	fin.close();
	fout.close();
	return 0;
}