Cod sursa(job #1831599)

Utilizator eilerGabriel-Ciprian Stanciu eiler Data 18 decembrie 2016 13:14:40
Problema Sortare topologica Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
#include <vector>
#include <fstream>
using namespace std;

int N, M, Qi;
vector <int> A[50000];
vector <int> E, Q;

int main(){
	int i, j, k;

	ifstream fin ("sortaret.in");
	fin >> N >> M;
	for (i=0; i<N; i++)
		A[i].resize(N);
	E.resize(N); Q.resize(N);
	for (k=0; k<M; k++){
		fin >> i >> j;
		i--; j--;
		A[i][j]++;
		E[j]++;
	}
	fin.close();

	while (Qi!=N){
		k=0;
		while (k<N && E[k]!=0)
			k++;
		if (k!=N){
			for (i=0; i<N; i++)
				if (A[i][k]!=0)
					A[i][k]=0;
				else if (A[k][i]!=0){
					E[i]-=A[k][i];
					A[k][i]=0;
				}
			Q[Qi++]=k;
			E[k]=-1;
		}
	}

	ofstream fout ("sortaret.out");
	for (i=0; i<N; i++)
		fout << Q[i]+1 << ' ';
	fout.close();

	return 0;
}