Cod sursa(job #3221330)

Utilizator DobraVictorDobra Victor Ioan DobraVictor Data 6 aprilie 2024 19:42:58
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.41 kb
#include <iostream>
#include <fstream>
#include <stdint.h>
#include <vector>

const int32_t MAX_N = 100000;

std::vector<int32_t> adj[MAX_N];
std::vector<int32_t> adjt[MAX_N];
int32_t used[MAX_N];
int32_t sort[MAX_N], top;

std::vector<int32_t> comps[MAX_N];
int32_t compTop = 0;

void SortDFS(int32_t node) {
	used[node] = 1;

	for(int32_t next : adjt[node])
		if(!used[next])
			SortDFS(next);
	
	sort[top++] = node;
}
void PlusDFS(int32_t node) {
	used[node] = 1;
	comps[compTop].push_back(node);

	for(int32_t next : adj[node])
		if(!used[next])	
			PlusDFS(next);
}
void MinusDFS(int32_t node) {
	used[node] = 2;

	for(int32_t next : adjt[node])
		if(used[next] == 1)
			MinusDFS(next);
}

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);
		adjt[y].push_back(x);
	}

	for(int32_t i = 0; i != n; ++i) {
		if(!used[i])
			SortDFS(i);
	}
	for(int32_t i = 0; i != n; ++i)
		used[i] = 0;

	while(--top != -1) {
		if(used[top])
			continue;
		
		PlusDFS(sort[top]);
		MinusDFS(sort[top]);
		++compTop;
	}

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

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

	return 0;
}