Cod sursa(job #2759193)

Utilizator PinkiePie1189Preoteasa Mircea-Costin PinkiePie1189 Data 15 iunie 2021 22:04:45
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.49 kb
#include <iostream>
#include <fstream>
#include <stack>
#include <cstring>
#include <vector>

#define IN_FILENAME "ctc.in"
#define OUT_FILENAME "ctc.out"


#define MAXV 100000

std::vector <int> G[MAXV + 1];
std::vector <int> Gt[MAXV + 1];


bool visited[MAXV + 1];

std::stack <int> topological_sort;


std::vector <std::vector <int>> sol;
std::vector <int> partial_sol;


void dfs(int node) {
	for (int i = 0; i < G[node].size(); i++) {
		int vec = G[node][i];

		if (!visited[vec]) {
			visited[vec] = true;
			dfs(vec);
		}
	}

	topological_sort.push(node);
}

void kosaraju(int node) {
	for (int i = 0; i < Gt[node].size(); i++) {
		int vec = Gt[node][i];

		if (!visited[vec]) {
			visited[vec] = true;
			partial_sol.push_back(vec);
			kosaraju(vec);
		}
	}
}

int main() {
	int V, E;
	std::ifstream input(IN_FILENAME);

	input >> V >> E;


	for (int i = 0; i < E; i++) {
		int x, y;
		input >> x >> y;
		G[x].push_back(y);
		Gt[y].push_back(x);
	}


	for (int i = 1; i <= V; i++) {
		if (!visited[i]) {
			visited[i] = true;
			dfs(i);
		}
	}


	memset(visited, 0, MAXV + 1);

	while (!topological_sort.empty()) {
		int curr = topological_sort.top();
		topological_sort.pop();
		if (!visited[curr]) {
			partial_sol.clear();
			visited[curr] = true;
			partial_sol.push_back(curr);
			kosaraju(curr);
			sol.push_back(partial_sol);
		}
	}

	std::ofstream output(OUT_FILENAME);
	output << sol.size() << "\n";
	for (auto &comp : sol) {
		for (auto &node : comp) {
			output << node << " ";
		}
		output << "\n";
	}

}