Cod sursa(job #3309601)

Utilizator LucaMuresanMuresan Luca Valentin LucaMuresan Data 6 septembrie 2025 22:27:37
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.99 kb
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>

using ll = long long;
#define debug(x) #x << " = " << x << '\n'

struct SCC { // 0-indexed
	int n;
	std::vector<std::vector<int>> g, gg;
	std::vector<int> order, cur;
	std::vector<bool> vis;
	std::vector<int> root;
	std::vector<std::vector<int>> comp;

	void init(int _n) {
		n = _n;
		g.resize(n);
		gg.resize(n);
		order.resize(n);
		order.clear();
		cur.clear();
		root.resize(n);
	}
	void reset() {
		order.clear();
		cur.clear();
		comp.clear();
		for (int i = 0; i < n; i++) {
			g[i].clear();
			gg[i].clear();
		}
	}

	void addEdge(int u, int v) {
		g[u].push_back(v);
		gg[v].push_back(u);
	}

	void dfs0(int u) {
		vis[u] = true;
		for (int v : g[u]) {
			if (!vis[v]) {
				dfs0(v);
			}
		}
		order.push_back(u);
	}

	void dfs(int u) {
		vis[u] = true;
		cur.push_back(u);
		for (int v : gg[u]) {
			if (!vis[v]) {
				dfs(v);
			}
		}
	}

	void build() {
		vis.assign(n, false);
		for (int i = 0; i < n; i++) {
			if (!vis[i]) {
				dfs0(i);
			}
		}
		vis.assign(n, false);
		std::reverse(order.begin(), order.end());
		for (int u : order) { 
			if (!vis[u]) {
				cur.clear();
				dfs(u);
				for (int v : cur) {
					root[v] = cur[0];
				}
				comp.push_back(cur);
			}
		}

		for (auto &v : comp) {
			std::sort(v.begin(), v.end());
		}
		std::sort(comp.begin(), comp.end(), [](auto u, auto v) {
			return u[0] < v[0];
		});
	}
};

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(0);
	std::cout.tie(0);

	freopen("ctc.in", "r", stdin);
	freopen("ctc.out", "w", stdout);

	SCC G;

	int n, m;
	std::cin >> n >> m;
  
	G.init(n);

	for (int i = 0; i < m; i++) {
		int u, v;
		std::cin >> u >> v;
		u--, v--;
		G.addEdge(u, v);
	}

	G.build();

	std::cout << (int) G.comp.size() << '\n';
	for (auto v : G.comp) {
		for (int x : v) {
			std::cout << x + 1 << ' ';
		}
		std::cout << '\n';
	}
	
  return 0;
}