Cod sursa(job #3359180)

Utilizator nverde1119Popa Narcis Constantin nverde1119 Data 25 iunie 2026 20:20:43
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.04 kb
#include <fstream>
#include <vector>

using namespace std;
const int NMAX = 100001;
int N, M, nrc;
ifstream f("ctc.in");
ofstream g("ctc.out");
vector<int> G[NMAX], GT[NMAX], CTC[NMAX], Post;
bool viz[NMAX];
void citire()
{
	f >> N >> M;
	int x, y;
	while(M--)
	{
		f >> x >> y;
		G[x].push_back(y);
		GT[y].push_back(x);
	}
}
void dfs(int x)
{
	viz[x] = 1;
	for(const auto &i : G[x])
	{
		if(viz[i] == 0)
			dfs(i);
	}
	Post.push_back(x);
}
void dfsGT(int x)
{
	viz[x] = 0;
	CTC[nrc].push_back(x);
	for(const auto &i : GT[x])
	{
		if(viz[i] == 1)
			dfsGT(i);
	}
}
void componente()
{
	int i;
	for(i = 1; i <= N; i++)
	{
		if(viz[i] == 0)
			dfs(i);
	}
	for(i = Post.size() - 1; i >= 0; --i)
	{
		if(viz[Post[i]] == 1)
		{
			nrc++;
			dfsGT(Post[i]);
		}
	}
}
void afisare()
{
	g << nrc << '\n';
	for(int i = 1; i <= nrc; i++)
	{
		for(const auto &x : CTC[i])
			g << x << ' ';
		g << '\n';
	}
}
int main()
{
	citire();
	componente();
	afisare();
	f.close();
	g.close();
	return 0;
}