Cod sursa(job #1590023)

Utilizator lorundlorund lorund Data 4 februarie 2016 17:27:09
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 3.82 kb
#include <iostream>
#include <utility>
#include <algorithm>
#include <vector>
#include <unordered_map>
#include <stack>
#include <queue>

template <class T>
class Graph{
public:
	std::vector<std::vector<T>> graph;
	unsigned nrNodes;
	unsigned nrEdges;
	std::vector<T> &operator[](unsigned node) {
		return graph[node];
	}
	bool Create(unsigned nrNodes) {
		graph.resize(nrNodes);
		this->nrNodes = nrNodes;
		return true;
	}
	bool TopologicalSort(std::vector<unsigned> &result) {
		std::stack<std::pair<unsigned, unsigned>> st;
		std::vector<bool> visited(graph.size());
		unsigned tr;

		for (tr = 0; tr<nrNodes; ++tr) {
			if (!visited[tr]) {
				st.push(std::make_pair(tr, 0));
				visited[tr] = true;
				while (st.size()) {
					unsigned gr = st.top().first; // current node
					unsigned &br = st.top().second; // adjacency list index

					if (br < graph[gr].size()) {
						if (!visited[graph[gr][br]]) {
							visited[graph[gr][br]] = true;
							st.push(std::make_pair(graph[gr][br], 0));
						}
						++br;
					}
					else {
						st.pop();
						result.push_back(gr);
					}
				}
			}
		}
		std::reverse(result.begin(), result.end());

		return true;
	}
	bool ConnectedComponents(std::vector<std::vector<unsigned>> &components) {
		std::vector<unsigned> parent;
		unsigned parentFrom, parentTo, index;
		std::unordered_map<unsigned, unsigned> componentIndex;

		for (unsigned i = 0; i<nrNodes; ++i) {
			parent.push_back(i);
		}

		for (unsigned i = 0; i<nrNodes; ++i) {
			for (unsigned j = 0; j<graph[i].size(); ++j) {
				parentFrom = i;
				parentTo = graph[i][j];

				while (parent[parentFrom] != parentFrom) {
					parentFrom = (parent[parentFrom] = parent[parent[parentFrom]]);
				}
				while (parent[parentTo] != parentTo) {
					parentTo = (parent[parentTo] = parent[parent[parentTo]]);
				}
				if (parentFrom != parentTo) {
					parent[parentFrom] = parentTo;
				}
			}
		}

		for (unsigned i = 0; i<nrNodes; ++i) {
			parentFrom = parent[i];
			while (parent[parentFrom] != parentFrom) {
				parentFrom = (parent[parentFrom] = parent[parent[parentFrom]]);
			}
			if (!componentIndex.count(parentFrom)) {
				unsigned index = componentIndex.size();
				componentIndex[parentFrom] = index;
				components.push_back(std::vector<unsigned>());
			}
			index = componentIndex[parentFrom];
			components[index].push_back(i);
		}
		return true;
	}
	bool StrongComponents(std::vector<std::vector<unsigned>> &components) {
		std::vector<unsigned> tsorted;
		std::vector<std::vector<unsigned>> tgraph(graph.size());;
		std::vector<bool> visited(graph.size());
		unsigned tr, gr, br;

		TopologicalSort(tsorted);
		for (tr = 0; tr<graph.size(); ++tr) {
			for (gr = 0; gr<graph[tr].size(); ++gr) {
				tgraph[graph[tr][gr]].push_back(tr);
			}
		}
		for (tr = 0; tr<tsorted.size(); ++tr) {
			if (!visited[tsorted[tr]]) {
				components.push_back(std::vector<unsigned>());
				std::vector<unsigned> &component = components.back();

				component.push_back(tsorted[tr]);
				visited[tsorted[tr]] = true;
				for (gr = 0; gr<component.size(); ++gr) {
					for (br = 0; br<tgraph[component[gr]].size(); ++br) {
						if (!visited[tgraph[component[gr]][br]]) {
							visited[tgraph[component[gr]][br]] = true;
							component.push_back(tgraph[component[gr]][br]);
						}
					}
				}
			}
		}

		return true;
	}
};

int main(int argc, char *argv[])
{
    int n, m;
	Graph<int> g;
	std::vector<unsigned> tsorted;

	freopen("sortaret.in", "r", stdin);
	freopen("sortaret.out", "w", stdout);

	scanf("%d %d", &n, &m);
	g.Create(n);
	for (int i=0; i<m; ++i){
	    int x, y;

        scanf("%d %d", &x, &y);
        g[x-1].push_back(y-1);
	}
	g.TopologicalSort(tsorted);
	for (int i=0; i<n; ++i){
	    printf("%d ", tsorted[i]+1);
	}

	return 0;
}