Cod sursa(job #1330766)

Utilizator MarianMMorosac George Marian MarianM Data 30 ianuarie 2015 22:37:41
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.62 kb
#define _CRT_SECURE_NO_DEPRECATE

#include <iostream>
#include <cstdio>
#include <list>		// Varianta 1 = V1 / Introduction to Alg: DFS, lista by finish time
#include <vector>   // Varianta 2 = V2 / Infoarena: Queue by 0-inDegree
#include <typeinfo>
using namespace std;

#define DMAX 50003

int N, M, timeR; // timeR is for V1
list<int> L; // V1
vector<int> Q; // V2 - "coada" 

struct Nod{
	int d, f, u, inDegree;
	vector<int> Adj; // outList
}G[DMAX];

void citire(){
	int i, j, x, y;

	cin >> N >> M;
	for (i = 0; i < M; i++){
		cin >> x >> y;
		G[x].Adj.push_back(y);
		G[y].inDegree++;
	}
}

void DFS(int root){
	int i, lg = G[root].Adj.size(), chld;

	G[root].d = ++timeR;
	G[root].u = 1;

	for (i = 0; i < lg; i++){
		chld = G[root].Adj[i];
		if (!G[chld].u){
			DFS(chld);
		}
	}

	G[root].f = ++timeR;
	L.push_front(root);
}
void solve_V1(){
	for (int i = 1; i <= N; i++){
		if (!G[i].inDegree){
			DFS(i);
		}
	}
}

void solve_V2(){
	int i, j, lg, chld;

	for (i = 1; i <= N; i++){
		if (!G[i].inDegree)
			Q.push_back(i);
	}

	for (i = 0; i < Q.size(); i++){ // Q.size() creste pana am parcurs toate vf
		lg = G[Q[i]].Adj.size();
		for (j = 0; j < lg; j++){
			chld = G[Q[i]].Adj[j];
			if (--G[chld].inDegree == 0){
				Q.push_back(chld);
			}
		}
	}
}

int main(){

	freopen("sortaret.in", "r", stdin);
	freopen("sortaret.out", "w", stdout);

	citire();

	if (N % 2){ // alegere "random"
		solve_V1(); // DFS, lista

		for (auto i : L) cout << i << ' ';
	}
	else{
		solve_V2(); // inDegree =0, Queue

		for (auto i : Q) cout << i << ' ';
	}

	return 0;
}