Cod sursa(job #3322643)

Utilizator raulthestormIlie Raul Ionut raulthestorm Data 15 noiembrie 2025 10:11:52
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.43 kb
#include <fstream>
#include <vector>
#include <stack>

using namespace std;
const int NMAX = 100000;

int N, M, nrc;

vector<int> G[NMAX + 1], CTC[NMAX + 1];
int D[NMAX + 1], Dmin[NMAX + 1], Timp = 0;

stack<int> S;
bool inSt[NMAX + 1]; ///inSt[i] = 1 <==> i este in stiva

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

void citire()
{
	int x, y;
	f >> N >> M;
	for(int i = 1; i <= M; i++)
	{
		f >> x >> y;
		G[x].push_back(y);
	}
}

void DFS(int x) ///Tarjan
{
	D[x] = ++Timp;
	Dmin[x] = D[x];
	S.push(x);
	inSt[x] = 1;
	for(auto &y : G[x])
	{
		if(D[y] == 0) ///Muchie de arbore
		{
			DFS(y);
			Dmin[x] = min(Dmin[x], Dmin[y]);
		}
		else
		{
			if(inSt[y] == 1) ///Muchie de intoarcere
				Dmin[x] = min(Dmin[x], D[y]);
			///Altfel este o muchie inainte sau muchie cross catre alta componenta conexa
		}
	}
	//
	///Daca x nu poate urca mai sus de x, atunci el este radacine unei CTC
	if(Dmin[x] == D[x]) ///x este radacina unei CTC
	{
		int u;
		nrc++;
		do            ///Scoatem nodurile CTC de pe stiva
		{
			u = S.top();
			CTC[nrc].push_back(u);
			S.pop();
			inSt[u] = 0;
		}
		while(x != u);
	}
}

void afisare()
{
	g << nrc << '\n';
	for(int i = 1; i <= nrc; ++i)
	{
		for(auto &x : CTC[i])
			g << x << ' ';
		g << '\n';
	}
}

int main()
{
	citire();
	for(int i = 1; i <= N; ++i)
	{
		if(D[i] == 0)
			DFS(i);
	}
	afisare();
	f.close();
	g.close();
	return 0;
}