Cod sursa(job #1436379)

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

using namespace std;

class Graph {

private:
	vector<int> *adjList;
	int nr_of_nodes;

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;
		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;
	}

};



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();
	//g.BFS(1);
	return 0;
}