Cod sursa(job #3285417)

Utilizator andrei_C1Andrei Chertes andrei_C1 Data 12 martie 2025 20:28:38
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.06 kb
#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> adj, adjt, ctc;
vector<bool> vis;
vector<int> ord;

void dfs(int u) {
	vis[u] = true;
	for(const auto &it : adj[u]) if(!vis[it]) {
		dfs(it);
	}
	ord.emplace_back(u);
}

void dfst(int u) {
	vis[u] = true;
	ctc.back().emplace_back(u);
	for(const auto &it : adjt[u]) if(!vis[it]) {
		dfst(it);
	}
}

int main() {
	cin.tie(nullptr)->sync_with_stdio(false);
#ifdef INFOARENA
	freopen("ctc.in", "r", stdin);
	freopen("ctc.out", "w", stdout);
#endif
	int n, m;
	cin >> n >> m;
	adj.resize(n);
	adjt.resize(n);
	for(int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		u--; v--;
		adj[u].emplace_back(v);
		adjt[v].emplace_back(u);
	}
	vis.resize(n);
	for(int i = 0; i < n; i++) if(!vis[i]) {
		dfs(i);
	}
	reverse(ord.begin(), ord.end());
	fill(vis.begin(), vis.end(), false);
	for(const auto &it : ord) if(!vis[it]) {
		ctc.emplace_back(vector<int>(0));
		dfst(it);
	}
	cout << ctc.size() << '\n';
	for(const auto &it : ctc) {
		for(const auto &it2 : it) {
			cout << it2 + 1 << " ";
		}
		cout << '\n';
	}
	return 0;
}