Cod sursa(job #2469107)

Utilizator SandruMariaMaria Sandru SandruMaria Data 6 octombrie 2019 15:21:13
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.53 kb
//#include "pch.h"
#include <iostream>
#include <deque>
#include <stack>
#include <queue>
#include <fstream>
using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
#define MAXE 50001
struct vertex {
	int weight;
	int value;
	vertex * next;
};
class Graph {
private:
	deque<vertex *> adjacencyList;
	deque<int> degree;
	deque<bool>processed;
	deque<bool>discovered;
	int nVertices, nEdges;
	bool directed;
public:
	void initialiseGraph() {
		for (int i = 1; i <= nVertices + 1; ++i) {
			adjacencyList.push_back(nullptr);
			degree.push_back(0);
			discovered.push_back(false);
			processed.push_back(false);
		}
	}
	void readGraph(int nVertices, int nEdges, bool directed) {
		int x, y;
		this->nVertices = nVertices;
		this->nEdges = nEdges;
		this->directed = directed;
		initialiseGraph();
		for (int i = 1; i <= nEdges; ++i) {
			fin >> x >> y;
			insertEdge(y, x, directed);
		}
	}
	void insertEdge(int x, int y, bool directed) {
		vertex * newVertex = new vertex;
		newVertex->value = x;
		newVertex->weight = 0;
		newVertex->next = adjacencyList.at(y);
		adjacencyList.at(y) = newVertex;
		if (directed == false) {
			insertEdge(y, x, !directed);
		}
	}
	void printAdjacencyList() {
		vertex * aux;
		for (int i = 0; i <= nVertices; ++i) {
			if (adjacencyList.at(i) != nullptr)
				fout << i << " : ";
			aux = adjacencyList.at(i);
			while (aux != nullptr) {
				fout << aux->value << " ";
				aux = aux->next;
			}
			fout << endl;
		}
	}
	void breadthFirstSearch(int start) {
		queue<int>vertices;
		deque<bool>vertexProcessed;
		deque<bool>vertexDiscovered;
		for (int i = 1; i <= nVertices + 1; ++i) {
			vertexProcessed.push_back(false);
			vertexDiscovered.push_back(false);
		}
		vertices.push(start);
		while (!vertices.empty()) {
			int x = vertices.front();
			vertexProcessed.at(x) = true;
			vertices.pop();
			vertex * aux = adjacencyList.at(x);
			while (aux != nullptr) {
				int y = aux->value;
				if (vertexProcessed.at(y) == false || directed == true) {
					fout << x << " -> " << y << endl;
				}
				if (vertexDiscovered.at(y) == false) {
					vertexDiscovered.at(y) = true;
					vertices.push(y);
				}
				aux = aux->next;
			}
		}
	}
	void depthFirstSearch(int start) {
		vertex * aux;
		aux = adjacencyList.at(start);
		while (aux != nullptr) {
			int x = aux->value;
			if (discovered.at(x) == false) {
				fout << start << " -> " << x << endl;
				discovered.at(x) = true;
				depthFirstSearch(x);
			}
			else if (processed.at(x) == false || directed == true) {
				fout << start << " -> " << x << endl;
			}
			aux = aux->next;
		}
		processed.at(start) = true;
	}
	void topSortHelper(int v, bool found[], stack<int> &sortedVertices) {
		found[v] = true;
		vertex * aux = adjacencyList.at(v);
		while (aux != nullptr) {
			if (found[aux->value] == false)
				topSortHelper(aux->value, found, sortedVertices);
			aux = aux->next;
		}
		sortedVertices.push(v);
	}
	void topologicalSort() {
		stack<int> sortedVertices;
		bool * found = new bool[nEdges + 1];
		for (int i = 1; i <= nVertices; i++)
			found[i] = false;

		for (int i = 1; i <= nVertices; i++)
			if (found[i] == false)
				topSortHelper(i, found, sortedVertices);

		while (sortedVertices.empty() == false)
		{
			fout << sortedVertices.top() << " ";
			sortedVertices.pop();
		}
	}
};
int main()
{
	int nVertices, nEdges;
	fin >> nVertices >> nEdges;
	Graph g;
	g.readGraph(nVertices, nEdges, true);
	g.topologicalSort();
	return 0;

}