Cod sursa(job #3030684)

Utilizator the_horoHorodniceanu Andrei the_horo Data 17 martie 2023 20:09:56
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.13 kb
#include <bits/stdc++.h>
using namespace std;

array<int, 100'010> level, low;

array<vector<int>, 100'010> edges;

vector<vector<int>> result;

void dfs(int node) {
	static stack<int> comp;
	static array<bool, 100'010> in_stack;
	static int memory = 0;
	

	low[node] = level[node] = memory ++;
	comp.emplace(node);
	in_stack[node] = true;

	for (auto to: edges[node]) {
		if (level[to] == -1)
			dfs(to);

		if (in_stack[to])
			low[node] = min(low[node], low[to]);
	}

	if (level[node] == low[node]) {
		result.emplace_back();
		int last;
		do {
			result.back().emplace_back(last = comp.top());
			comp.pop();
			in_stack[last] = false;
		} while (last != node);
	}
}

int main () {
	ifstream in("ctc.in");
	in.exceptions(in.failbit);
	ofstream out("ctc.out");
	out.exceptions(out.failbit);

	int n, m;
	in >> n >> m;

	for (int i = 0; i < m; ++ i) {
		int x, y;
		in >> x >> y;

		edges[x].emplace_back(y);
	}

	std::fill_n(level.begin() + 1, n, -1);

	for (int i = 1; i <= n; ++ i)
		if (level[i] == -1)
			dfs(i);

	out << result.size() << '\n';

	for (const auto &comp: result) {
		for (const auto &node: comp)
			out << node << ' ';
		out << '\n';
	}
}