Cod sursa(job #3318850)

Utilizator DobraVictorDobra Victor Ioan DobraVictor Data 29 octombrie 2025 13:36:47
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.5 kb
#include <iostream>
#include <fstream>
#include <stdint.h>
#include <vector>

const int32_t MAX_N = 100000;
const int32_t MAX_M = 200000;

std::vector<int32_t> adj[MAX_N];
int32_t inds[MAX_N], lowInds[MAX_N], currInd = 0;
int32_t stack[MAX_N], top = 0;
bool onStack[MAX_N];
std::vector<int32_t> comps[MAX_N];
int32_t compCount = 0;

int32_t min(int32_t x, int32_t y) {
	return (x < y) ? x : y;
}
void DFS(int32_t node) {
	inds[node] = currInd;
	lowInds[node] = currInd;
	++currInd;

	stack[top++] = node;
	onStack[node] = true;

	for(int32_t next : adj[node]) {
		if(inds[next] == -1) {
			DFS(next);
			lowInds[node] = min(lowInds[node], lowInds[next]);
		} else if(onStack[next]) {
			lowInds[node] = min(lowInds[node], inds[next]);
		}
	}

	if(inds[node] == lowInds[node]) {
		do {
			int32_t last = stack[--top];
			onStack[last] = false;
			comps[compCount].push_back(last);
		} while(stack[top] != node);
		++compCount;
	}
}

int main() {
	std::ifstream fin("ctc.in");
	std::ofstream fout("ctc.out");

	int32_t n, m;
	fin >> n >> m;

	for(int32_t i = 0; i != m; ++i) {
		int32_t x, y;
		fin >> x >> y;
		--x; --y;

		adj[x].push_back(y);
	}
	for(int32_t i = 0; i != n; ++i)
		inds[i] = -1;
	
	for(int32_t i = 0; i != n; ++i) {
		if(inds[i] == -1)
			DFS(i);
	}

	fout << compCount << '\n';
	for(int32_t i = 0; i != compCount; ++i) {
		for(int32_t node : comps[i])
			fout << (node + 1) << ' ';
		fout << '\n';
	}

	fin.close();
	fout.close();

	return 0;
}