Cod sursa(job #2971807)

Utilizator rastervcrastervc rastervc Data 28 ianuarie 2023 08:52:22
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.1 kb
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

ifstream fin("ctc.in");
ofstream fout("ctc.out");

constexpr size_t LIM = 100005;
int N, M, node1, node2, i;
vector<int> G[LIM], GT[LIM];
vector<vector<int>> scc;
bool vis[LIM], vis_t[LIM];
stack<int> st;

static void dfs1(int node) {
	vis[node] = true;
	for (const int adj : G[node])
		if (!vis[adj]) dfs1(adj);
	st.push(node);
}

static void dfs2(int node) {
	vis_t[node] = true;
	scc.back().push_back(node);
	for (const int adj : GT[node])
		if (!vis_t[adj]) dfs2(adj);
}

int main() {
	fin >> N >> M;
	for (i = 1; i <= M; ++i) {
		fin >> node1 >> node2;
		G[node1].push_back(node2);
		GT[node2].push_back(node1);
	}

	for (i = 1; i <= N; ++i)
		if (!vis[i]) dfs1(i);

	while (!st.empty()) {
		const int node = st.top();
		if (!vis_t[node]) {
			scc.emplace_back();
			dfs2(node);
		}
		st.pop();
	}

	fout << scc.size() << '\n';
	for (const auto& component : scc) {
		for (const int node : component)
			fout << node << ' ';
		fout << '\n';
	}

	fin.close();
	fout.close();
	return 0;
}