Cod sursa(job #3297096)

Utilizator raresgoidescuGoidescu Rares-Stefan raresgoidescu Data 20 mai 2025 23:36:36
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.52 kb
#include <iostream>
#include <vector>
#include <stack>

const int MAXN = 100005;

int n, m;
std::vector<int> adj[MAXN];
std::stack<int> st;
int timestamp;
int finish[MAXN];
int low_link[MAXN];
bool on_stack[MAXN];
std::vector<std::vector<int> > ans;

void rec_tarjan(int node)
{
	finish[node] = low_link[node] = timestamp++;
	st.push(node);
	on_stack[node] = true;

	for (int neigh : adj[node]) {
		if (finish[neigh] == -1) {
			rec_tarjan(neigh);
			low_link[node] =
				std::min(low_link[node], low_link[neigh]);
		} else if (on_stack[neigh]) {
			low_link[node] =
				std::min(low_link[node], finish[neigh]);
		}
	}

	if (low_link[node] == finish[node]) {
		std::vector<int> current_scc;
		while (true) {
			int node_from_stack = st.top();
			st.pop();
			on_stack[node_from_stack] = false;
			current_scc.push_back(node_from_stack);
			if (node_from_stack == node) {
				break;
			}
		}
		ans.push_back(current_scc);
	}
}

int main(void)
{
#ifndef LOCAL
	freopen("ctc.in", "r", stdin);
	freopen("ctc.out", "w", stdout);
#endif

	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);

	std::cin >> n >> m;

	for (int i = 0; i < m; ++i) {
		int u, v;

		std::cin >> u >> v;

		adj[u].push_back(v);
	}

	for (int i = 1; i <= n; ++i) {
		finish[i] = -1;
	}

	for (int i = 1; i <= n; ++i) {
		if (finish[i] == -1) {
			rec_tarjan(i);
		}
	}

	std::cout << ans.size() << "\n";
	for (const auto &scc : ans) {
		for (size_t i = 0; i < scc.size(); ++i) {
			std::cout << scc[i] << (i == scc.size() - 1 ? "" : " ");
		}
		std::cout << "\n";
	}

	return 0;
}