Cod sursa(job #2372850)

Utilizator DeleDelegeanu Alexandru Dele Data 7 martie 2019 11:19:47
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.05 kb
#include <fstream>
#include <vector>
#include <stack>

std::ifstream f("ctc.in");
std::ofstream g("ctc.out");

class Graph {
private:
	int V;
	std::vector<int>* table;
	std::vector<int>* reverseTable;

private:
	void DFS(int vertex, std::vector<bool>&visited, std::stack<int>&Stack) {
		visited[vertex] = true;

		std::vector<int>::iterator itEnd = table[vertex].end();
		for (std::vector<int>::iterator it = table[vertex].begin(); it != itEnd; ++it) {
			if (!visited[*it])
				DFS(*it, visited, Stack);
		}

		Stack.push(vertex);
	}

	void reverseDFS(int vertex, std::vector<bool>&visited, std::vector<int>&component) {
		visited[vertex] = false;
		component.push_back(vertex);

		std::vector<int>::iterator itEnd = reverseTable[vertex].end();
		for (std::vector<int>::iterator it = reverseTable[vertex].begin(); it != itEnd; ++it) {
			if (visited[*it])
				reverseDFS(*it, visited, component);
		}
	}

public:
	Graph(int numberOfVertices) {
		V = numberOfVertices + 1;
		table = new std::vector<int>[V];
		reverseTable = new std::vector<int>[V];
	}

	void addEdge(int x, int y) {
		table[x].push_back(y);
		reverseTable[y].push_back(x);
	}

	void SCC() {
		std::stack<int> Stack;
		std::vector<bool> visited(V, false);

		for (int i = 1; i < V; ++i)
			if (!visited[i])
				DFS(i, visited, Stack);

		std::vector<std::vector<int>> components;
		while (!Stack.empty()) {
			int vertex = Stack.top();
			Stack.pop();

			if (visited[vertex]) {
				std::vector<int> component;
				reverseDFS(vertex, visited, component);
				components.push_back(component);
			}
		}

		int nrC = components.size();
		g << nrC << '\n';
		for (int i = 0; i < nrC; ++i) {
			for (std::vector<int>::iterator it = components[i].begin(); it != components[i].end(); ++it) {
				g << *it << " ";
			}
			g << '\n';
		}
	}
};

int main() {
	int n;
	f >> n;

	Graph *myGraph = new Graph(n);

	int m;
	f >> m;

	int x, y;
	for (int i = 1; i <= m; ++i) {
		f >> x >> y;
		myGraph->addEdge(x, y);
	}

	myGraph->SCC();

	return 0;
}