Cod sursa(job #3372216)

Utilizator Alex112358Glavan Alexandru Alex112358 Data 2 noiembrie 2026 19:08:49
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.12 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

ifstream f("ctc.in");
ofstream g("ctc.out");

int N, M, nrComponente;
vector<vector<int>> componenete;
vector<int> G[100001], GT[100001], viz, ordine, viz2;

void dfsG(int nod){
	viz[nod] = 1;

	for (auto vecin : G[nod])
		if (viz[vecin] == 0)
			dfsG(vecin);
	ordine.push_back(nod);
}

void dfsGT(int nod) {
	
	viz2[nod] = 1;
	componenete[nrComponente].push_back(nod);
	for (auto vecin : GT[nod])
		if (viz2[vecin] == 0)
			dfsGT(vecin);
	

}

int main() {

	f >> N >> M;
	componenete.resize(N+1);
	viz.resize(N + 1);
	viz2.resize(N + 1);
	for (int i = 1; i <= M; i++)
	{
		int n1, n2;
		f >> n1 >> n2;
		G[n1].push_back(n2);
		GT[n2].push_back(n1);
	}


	for (int i = 1; i <= N; i++)
		if (viz[i] == 0)
			dfsG(i);

	for(int i = ordine.size() - 1 ; i >= 0 ; i--)
		if (viz2[ordine[i]] == 0)
		{
			nrComponente++;
			dfsGT(ordine[i]);
		}
	
	g << nrComponente << "\n";
	for (int i = 1; i <= nrComponente; i++)
	{
		for (auto nod : componenete[i])
			g <<  nod<< " ";
		g << "\n";
	}
	return 0;
}