Cod sursa(job #1436585)

Utilizator ramhackNastase Ramon ramhack Data 16 mai 2015 07:24:07
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.23 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, stack<int> &topSortStack ) {

		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, topSortStack);
			}
		}
		topSortStack.push(node);
	}

	void DFS() {

		stack<int> Stack;

		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,Stack);
			}
		}
		delete[] visited;
	
		while(!Stack.empty()) {

		    cout << Stack.top() << " ";
		    Stack.pop();
		}
	}

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

};



int main(int argc, char const *argv[])
{
	freopen("sortaret.in", "r", stdin);
	//freopen("test.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;
}