Cod sursa(job #3342966)

Utilizator DobraVictorDobra Victor Ioan DobraVictor Data 26 februarie 2026 11:09:55
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.2 kb
#include <iostream>
#include <fstream>
#include <stdint.h>

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

int32_t min(int32_t x, int32_t y) {
	return (x < y) ? x : y;
}

struct Node {
	int32_t adjStart;
	int32_t timeIn, maxClimb;
	bool onStack;
};
struct AdjItem {
	int32_t node;
	int32_t next;
};

int32_t n, m;
Node nodes[MAX_N];
AdjItem adj[MAX_M];

int32_t stack[MAX_N], top = 0, globalTime = 0;
int32_t compCount;
int32_t compStarts[MAX_N + 1], compNodes[MAX_N];

void ReadGraph(std::istream& fin) {
	fin >> n >> m;

	for(int32_t i = 0; i != n; ++i)
		nodes[i].adjStart = -1;
	for(int32_t i = 0; i != m; ++i) {
		int32_t x, y;
		fin >> x >> y;
		--x; --y;

		adj[i].node = y;
		adj[i].next = nodes[x].adjStart;
		nodes[x].adjStart = i;
	}
}
void DFSFindSCC(int32_t node) {
	nodes[node].timeIn = globalTime;
	nodes[node].maxClimb = globalTime;
	++globalTime;

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

	for(int32_t ind = nodes[node].adjStart; ind != -1; ind = adj[ind].next) {
		int32_t next = adj[ind].node;

		if(nodes[next].timeIn == -1) {
			DFSFindSCC(next);
			nodes[node].maxClimb = min(nodes[node].maxClimb, nodes[next].maxClimb);
		} else if(nodes[next].onStack) {
			nodes[node].maxClimb = min(nodes[node].maxClimb, nodes[next].timeIn);
		}
	}

	if(nodes[node].maxClimb == nodes[node].timeIn) {
		int32_t compNode;
		int32_t compTop = compStarts[compCount];

		do {
			compNode = stack[--top];
			nodes[compNode].onStack = false;
			compNodes[compTop++] = compNode;
		} while(compNode != node);

		++compCount;
		compStarts[compCount] = compTop;
	}
}
void FindSCC() {
	for(int32_t i = 0; i != n; ++i)
		nodes[i].timeIn = -1;
	
	for(int32_t i = 0; i != n; ++i) {
		if(nodes[i].timeIn == -1)
			DFSFindSCC(i);
	}
}
void OutputRes(std::ostream& fout) {
	fout << compCount << '\n';

	for(int32_t i = 0; i != compCount; ++i) {
		for(int32_t j = compStarts[i]; j != compStarts[i + 1]; ++j)
			fout << (compNodes[j] + 1) << ' ';
		fout << '\n';
	}
}

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

	ReadGraph(fin);
	FindSCC();
	OutputRes(fout);

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

	return 0;
}