Cod sursa(job #812104)

Utilizator RobertSSamoilescu Robert RobertS Data 13 noiembrie 2012 15:01:47
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
#define MAX_N 50000
vector<int>myvector[MAX_N];
int coada[MAX_N];
int deg[MAX_N];
int N, M;

void read_from_file(){
	ifstream f("sortare.in");
	f >> N >> M;
	int nod1, nod2;
	for(int i=1; i<=M; i++){
		f>> nod1 >> nod2;
		myvector[nod2].push_back(nod1);
		deg[nod1] ++;
	}
}

void write_to_file(){
	
	for(int i=N; i>0; i--){
		cout << coada[i] << " ";
	}
	
}

void solve(){
	for(int i=1; i<=N; i++){
		if(deg[i] == 0){
			coada[++coada[0]] = i;
		}
	}
	
	for(int i=1; i<=N; i++){
		int x =  coada[i];
		for(unsigned int j=0; j<myvector[x].size(); j++){
			deg[myvector[x][j]]--;
			if(deg[myvector[x][j]] == 0){
				coada[++coada[0]] =  myvector[x][j];
			}
		}
	
	}
	
	
}


int main(){
	read_from_file();
	solve();
	write_to_file();
return 0;
}