Cod sursa(job #3373961)

Utilizator lefterache_stefanLefterache Stefan lefterache_stefan Data 8 noiembrie 2026 13:03:40
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.75 kb
#include <bits/stdc++.h>

using namespace std;

ifstream input("ctc.in");
ofstream output("ctc.out");

int main() {
	int n, m;
	input >> n >> m;
	vector<vector<int>> graph(n + 1), components;

	for (int i = 0; i < m; ++i) {
		int from, to;
		input >> from >> to;
		graph[from].push_back(to);
	}

	vector<int> discovery(n + 1), low(n + 1), parent(n + 1), nextNeighbor(n + 1);
	vector<bool> inStack(n + 1);
	vector<int> dfsStack, componentStack;
	int timer = 0;

	for (int start = 1; start <= n; ++start) {
		if (discovery[start] != 0) {
			continue;
		}

		discovery[start] = low[start] = ++timer;
		inStack[start] = true;
		dfsStack.push_back(start);
		componentStack.push_back(start);

		while (!dfsStack.empty()) {
			const int node = dfsStack.back();

			if (nextNeighbor[node] < static_cast<int>(graph[node].size())) {
				const int neighbor = graph[node][nextNeighbor[node]++];
				if (discovery[neighbor] == 0) {
					parent[neighbor] = node;
					discovery[neighbor] = low[neighbor] = ++timer;
					inStack[neighbor] = true;
					dfsStack.push_back(neighbor);
					componentStack.push_back(neighbor);
				} else if (inStack[neighbor]) {
					low[node] = min(low[node], discovery[neighbor]);
				}
				continue;
			}

			dfsStack.pop_back();
			if (parent[node] != 0) {
				low[parent[node]] = min(low[parent[node]], low[node]);
			}

			if (low[node] == discovery[node]) {
				components.emplace_back();
				int current;
				do {
					current = componentStack.back();
					componentStack.pop_back();
					inStack[current] = false;
					components.back().push_back(current);
				} while (current != node);
			}
		}
	}

	output << components.size() << '\n';
	for (const auto& component : components) {
		for (const int node : component) {
			output << node << ' ';
		}
		output << '\n';
	}
}