Cod sursa(job #978031)

Utilizator petrutsxMihaela Petruta Gaman petrutsx Data 27 iulie 2013 16:14:12
Problema Sortare topologica Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include<fstream>
#include<vector>
#include<queue>
#define NMAX 5005
using namespace std;

ifstream f("sortaret.in");
ofstream g("sortaret.out");

int degree[NMAX], A[NMAX][NMAX];
vector <int> sol;
int N, M;
 
void read(){
	int X, Y, i, j;
	f>>N>>M;
	for(i = 1; i <= N; i++){
		for(j = 1; j <= N; j++)
			A[i][j] = 0;
		degree[i] = 0;
	}

	for(i = 1; i <= M; i++){
		f>>X>>Y;
		if(A[X][Y] == 0)
			degree[Y]++;

		A[X][Y] = 1;	
	}
}
 
void print(){	
	int i;
	for(i = 0; i < sol.size(); i++)
		g<<sol[i]<<' ';
}

void topo_sort(){	 
		queue<int> Q;
		int u, v;
	 
		for(u = 1; u <= N; u++){
			if(degree[u] == 0) 
				Q.push(u);
		} 
	 
		while(!Q.empty()){
			u = Q.front();
			Q.pop();
			sol.push_back(u);

			for(v = 1; v <= N; v++)
				if(A[u][v] == 1){
					degree[v]--;
					if(degree[v] == 0)
					Q.push(v);      
	            }  
	    }
	  
}
 
int main(){
	read();

	topo_sort();

	print();	

    return 0;
}