Cod sursa(job #2487802)

Utilizator SandruMariaMaria Sandru SandruMaria Data 5 noiembrie 2019 18:58:06
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.24 kb
// ST.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#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;
	stack<bool>discoveredTop;
	deque<bool>vertexDiscovered;

	int nVertices, nEdges;
	bool directed;
public:
	void initialiseGraph() {
		for (int i = 1; i <= MAXE; ++i) {
			adjacencyList.push_back(nullptr);
			degree.push_back(0);
			discovered.push_back(false);
			processed.push_back(false);
			vertexDiscovered.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;
		degree[x] ++;
		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 topologicalSort() {
		queue <int> edgeNodesQueue;
		int discovered[MAXE];
		for (int i = 1; i <= nVertices; ++i)
			discovered[i] = false;


		for (int i = 1; i <= nVertices; i++) {
			if (degree[i] == 0) {
				edgeNodesQueue.push(i);
				discovered[i] = true;
			}
		}
		while (!edgeNodesQueue.empty()) {
			int x = edgeNodesQueue.front();
			edgeNodesQueue.pop();
			fout << x << " ";
			vertex * neighbor = adjacencyList.at(x);
			while (neighbor != nullptr) {
				degree[neighbor->value] = degree[neighbor->value] - 1;
				if (discovered[neighbor->value] == false && degree[neighbor->value] == 0) {
					edgeNodesQueue.push(neighbor->value);
					discovered[neighbor->value] = true;
				}
				neighbor = neighbor->next;
			}


		}

	}
};
int main()
{
	int nVertices, nEdges;
	fin >> nVertices >> nEdges;
	Graph g;
	g.readGraph(nVertices, nEdges, true);
	g.topologicalSort();
	return 0;

}

// Run program: Ctrl + F5 or Debug > Start Without Debugging menu
// Debug program: F5 or Debug > Start Debugging menu

// Tips for Getting Started: 
//   1. Use the Solution Explorer window to add/manage files
//   2. Use the Team Explorer window to connect to source control
//   3. Use the Output window to see build output and other messages
//   4. Use the Error List window to view errors
//   5. Go to Project > Add New Item to create new code files, or Project > Add Existing Item to add existing code files to the project
//   6. In the future, to open this project again, go to File > Open > Project and select the .sln file