Cod sursa(job #1457096)

Utilizator Baclava_Georgiana_Liliana_322CBBaclava Georgiana Liliana Baclava_Georgiana_Liliana_322CB Data 2 iulie 2015 17:49:53
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include <stdio.h>
#include <iostream>
#include <vector>

#define MAX 100000

using namespace std;

int N = 0, M = 0, count = 0;

vector <int> sortat, c(MAX+1);
vector <int> top[MAX];
vector <int>::iterator it;



void exporare(int u){
	c[u] = 1;

	for( int i = 1; i < top[u].size();i++){

		int v = top[u][i];
		if(v == 0) {
			break;
		}
		if(c[v] == 0) exporare(v);
		if(c[v] == 1){
			//printf("%s\n","Eroare:ciclu!");
			return;
		}
	}
	c[u] = 2;
	it = sortat.begin();
	it = sortat.insert(it,u);
}



void DFS(){
	for(int i = 0; i < N; i++){
		int u = i+1;
		if(c[u] == 0)
			exporare(u);
	}
}



int main(){

	freopen("sortaret.in","rt",stdin);
	freopen("sortaret.out","wt",stdout);

	cin >> N >> M;

	int x, y;

	for(int i = 0; i < M; i++){
		cin >> x >> y;
		top[x].push_back(y);
	}



	DFS();

	for(unsigned int i = 0; i < sortat.size(); i++){
		cout << sortat[i] << " ";
	}
	//cout << "\n";

	// for(int i = 1; i <= N; i++){
	// 	for(unsigned int j = 1; j <= top[i].size();j++){
	// 		if(top[i][j == 0]) break;
	// 		printf("%d\n", top[i][j]);
	// 	}
	// }
}