Cod sursa(job #1436397)

Utilizator ramhackNastase Ramon ramhack Data 15 mai 2015 20:44:46
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.01 kb
#include <iostream>
#include <cstdio>
#include <vector>
#include <list>
#include <stack>
#include <cstdlib>
#include <iterator>
#include <queue>
#include <list>

using namespace std;

class Graph {

private:
	vector<int> *adjList;
	int nr_of_nodes;
	list<int> topsortList;
public:
	Graph(int V) {
		nr_of_nodes = V;
		adjList = new vector<int>[V + 2];
	}
	~Graph() {
		delete[] adjList;
	}

	void addEdge(int u, int v) {
		adjList[u].push_back(v);
	}

	//just for fun
	void BFS(int root_node) {

		bool *visited = new bool[nr_of_nodes + 2];
		
		for (int i = 0; i < nr_of_nodes; ++i) {
			visited[i] = false;
		}

		queue<int> Q;
		vector<int>::iterator it;
		int node;

		visited[root_node] = true;
		Q.push(root_node);
		cout <<"\n";

		while(!Q.empty()) {
			
			node = Q.front();
			Q.pop();
			cout << node << " ";
			for(it = adjList[node].begin(); it != adjList[node].end(); it++) {

				if(visited[*it] == false) {

					visited[*it] = true;
					Q.push(*it);
				}
			}    
		}
	}


	void DFShelper(int node, bool *visited ) {

		visited[node] = true;
		topsortList.push_back(node);
		vector<int>::iterator it;

		//cout << node << " ";

		for(it = adjList[node].begin(); it != adjList[node].end(); it++) {

			if(visited[*it] == false) {

				DFShelper(*it, visited);
			}
		}
	}

	void DFS() {

		bool *visited = new bool[nr_of_nodes + 1];

		for(int i = 0; i < nr_of_nodes; i++) {
			visited[i] = false;
		}

		for(int node = 1; node <= nr_of_nodes; node++) {

			if(visited[node] == false) {
				DFShelper(node, visited);
			}
		}
		delete[] visited;
	}

	list<int> getTopSortList() {
		return this->topsortList;
	}

};



int main(int argc, char const *argv[])
{
	freopen("sortaret.in", "r", stdin);
	freopen("sortaret.out", "w", stdout);

	int N, M, x, y;

	scanf("%d %d", &N, &M);

	Graph g(N);

	for(int i = 0; i < M; i++) {
		scanf("%d %d", &x, &y);

		g.addEdge(x,y);
	}

	g.DFS();
	list<int> lst = g.getTopSortList();
	list<int>::iterator it;

	for(it = lst.begin(); it != lst.end(); ++it) {
		cout << *it << " ";
	}

	//g.BFS(1);
	return 0;
}