Cod sursa(job #784577)

Utilizator pascu_iulianPascu Iulian pascu_iulian Data 6 septembrie 2012 13:37:55
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.66 kb
#include "fstream"
#include "vector"
#define N 50000
#define M 100000
using namespace std;

vector <int> fii[N+1];
int grad[N+1], Q[N+1];
int n,m;

int main(){
	
	int i, x, a, b;
	ifstream fin("sortaret.in");
	
	fin >> n >> m;
	for (i = 0; i < m; ++i) {
		fin >> a >> b;
		++grad[b];
		fii[a].push_back(b);
	}
	
	fin.close();
	
	for (i = 1; i <= n; ++i) 
		if (grad[i] == 0) Q[ ++Q[ 0]] = i;
		
	for (i = 1; i <= n; ++i) {
		x = Q[i];
		for (vector<int>::iterator it = fii[x].begin(); it != fii[x].end(); ++it) {
			grad[*it]--;
			if ( grad[*it] == 0) Q[ ++Q[ 0]]= *it;
		}
	}
	
	ofstream fout("sortaret.out");
	
	for (i = 1; i <= n; ++i) 
		fout << Q[i] << ' ';
	
	return 0;
}