Cod sursa(job #341766)

Utilizator Binary_FireFlorin Pogocsan Binary_Fire Data 19 august 2009 15:16:50
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <queue>

using namespace std;

#define mp make_pair
#define pb push_back
#define sz(c) (int)((c).size())
#define f first
#define s second

#define fin  "sortaret.in"
#define fout "sortaret.out"

#define NMAX 50010

int N, M, inDeg[NMAX];
vector<int> g[NMAX];
queue<int> q;

void ReadData()
{
	int a, b;

	ifstream f(fin);

	f >> N >> M;
	for ( int i = 1; i <= M; ++i )
		f >> a >> b, g[a].pb(b), inDeg[b]++;

	f.close();
}

void Solve()
{
	int i, x;

	ofstream f(fout);

for ( i = 1; i <= N; ++i )
		if ( inDeg[i] == 0 ) q.push(i);

	while ( !q.empty() )
	{
		x = q.front();
		q.pop();
		f << x << " ";
		for ( i = 0; i < sz(g[x]); ++i )
		{
			--inDeg[ g[x][i] ];
			if ( inDeg[ g[x][i] ] == 0 )
				q.push( g[x][i] );
		}
	}

	f.close();
}

int main()
{
	ReadData();
	Solve();
	return 0;
}