Cod sursa(job #1199575)

Utilizator silidragosSilion Dragos silidragos Data 19 iunie 2014 17:35:27
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include<iostream>
#include<fstream>
#include<vector>
#include<queue>

#define NMAX 50100

using namespace std;

vector<int> G[NMAX];
queue<int> Q;
int deg[NMAX];

int N, M;

int main(){
	ifstream f("sortaret.in", ios::in);//Change the name
	ofstream g("sortaret.out", ios::out);//Change the name
	int a, b, x;
	f >> N >> M;
	for (int i = 0; i < M; ++i)
	{
		f >> a >> b;
		G[a].push_back(b);
		deg[b]++;
	}

	for (int i = 1; i <= N; ++i){
		if (deg[i] == 0) Q.push(i);
	}

	for (int i = 1; i <= N; ++i){
		x = Q.front();
		Q.pop();
		g << x << ' ';
		
		for (int i = 0; i < G[x].size(); ++i){
			deg[G[x][i]]--;
			if (deg[G[x][i]] == 0) Q.push(G[x][i]);
		}
	}




	f.close();
	g.close();
	return 0;
}