Cod sursa(job #2847051)

Utilizator lucamLuca Mazilescu lucam Data 10 februarie 2022 09:19:01
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.15 kb
#include <bits/stdc++.h>

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

const int N = 1e5;

int n, m;
std::vector<int> g[N], gt[N];
bool vis[N];

std::vector<int> topsort() {
	std::vector<int> res{{}};
	res.reserve(n);
	std::function<void(int)> dfs = [&](int u) {
		vis[u] = true;
		for (int v : g[u]) {
			if (!vis[v]) {
				dfs(v);
			}
		}
		res.push_back(u);
	};
	for (int u = 1; u <= n; ++u) {
		if (!vis[u]) {
			dfs(u);
		}
	}
	std::reverse(res.begin(), res.end());
	return res;
}

bool traverse_print = false;
void traverse_component(int u) {
	vis[u] = true;
	if (traverse_print) {
		out << u << ' ';
	}
	for (int v : gt[u]) {
		if (!vis[v]) {
			traverse_component(v);
		}
	}
}

int main() {
	in >> n >> m;
	for (int i = 0; i < m; ++i) {
		int u, v;
		in >> u >> v;
		g[u].push_back(v);
		gt[v].push_back(u);
	}
	auto topord = topsort();
	std::fill(vis + 1, vis + n + 1, false);
	int cnt = 0;
	for (int u : topord) {
		if (!vis[u]) {
			++cnt;
			traverse_component(u);
		}
	}
	out << cnt << '\n';
	std::fill(vis + 1, vis + n + 1, false);
	traverse_print = true;
	for (int u : topord) {
		if (!vis[u]) {
			traverse_component(u);
			out << '\n';
		}
	}
}