Cod sursa(job #978020)

Utilizator petrutsxMihaela Petruta Gaman petrutsx Data 27 iulie 2013 15:30:18
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
#include<fstream>
#include<vector>
#define NMAX 5001
using namespace std;

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

int col[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;
		col[i] = 0;
	}

	for(i = 1; i <= M; i++){
		f>>X>>Y;
		A[X][Y] = 1;
	}
}
 
void DFS(int u){
    int v;
	col[u] = 1;

	for(v = 1; v <= N; v++)
		if(A[u][v] == 1 && col[v] == 0)
			DFS(v);

	sol.push_back(u);
}

void print(){	
	int i;
	for(i = 0; i < sol.size(); i++)
		g<<sol[i]<<' ';
}
 
int main(){
	int i;
	read();
	for(i = 1; i <= N; i++)
		if(col[i] == 0)
			DFS(i);

	print();	

    return 0;
}