Cod sursa(job #2100926)

Utilizator belgun_adrianBelgun Dimitri Adrian belgun_adrian Data 6 ianuarie 2018 16:17:48
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.8 kb
#include <vector>
#include <list>
#include <fstream>
#include <iostream>

class GraphHelper {
public:
	static void reversePostorder(int k, const std::vector<std::list<int>>& edges, std::vector<bool>& marked, std::list<int>& out) {
		if (marked[k])
			return;
		marked[k] = true;
		for (int x : edges[k])
			reversePostorder(x, edges, marked, out);
		out.push_front(k);
	}

	static void preorder(int k, const std::vector<std::list<int>>& edges, std::vector<bool>& marked, std::list<int>& out) {
		if (marked[k])
			return;

		marked[k] = true;
		out.push_back(k);
		for (int x : edges[k])
			preorder(x, edges, marked, out);
	}
};

class DGraph {
public:
	DGraph(int _n) : n(_n), edge(_n), redge(_n) {}

	void add_edge(int u, int v) {
		edge[u].push_back(v);
		redge[v].push_back(u);
	}

	void kosaraju(std::list<std::list<int>>& out) {
		std::list<int> rpos;
		{
			std::vector<bool> marked(n, false);

			for (int i = 0; i < n; i++) {
				if (marked[i])
					continue;
				GraphHelper::reversePostorder(i, redge, marked, rpos);
			}
		}
		{
			std::vector<bool> marked(n, false);
			for (int x : rpos) {
				if (marked[x])
					continue;
				out.push_back(std::list<int>());
				GraphHelper::preorder(x, edge, marked, out.back());
			}
		}
	}

private:
	int n;
	std::vector<std::list<int>> edge;
	std::vector<std::list<int>> redge;
};


int main() {
	std::ifstream in("ctc.in");
	int n, m;
	in >> n >> m;
	
	DGraph g(n);
	for (int i = 0; i < m; i++) {
		int u, v;
		in >> u >> v;
		g.add_edge(u - 1, v - 1);
	}
	std::list<std::list<int>> components;
	g.kosaraju(components);

	std::ofstream out("ctc.out");
	out << components.size() << "\n";
	for (const auto& comp : components) {
		for (int x : comp)
			out << x + 1 << " ";
		out << "\n";
	}

	return 0;
}