Cod sursa(job #3364750)

Utilizator batasAndrei Batis batas Data 10 septembrie 2026 17:53:11
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.32 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <set>
using namespace std;
using VI = vector<int>;
using VB = vector<bool>;
using VVI = vector<VI>;

ifstream fin("ctc.in");
ofstream fout("ctc.out");

int n, m;
VB v;
set<int> currCmp;
VVI G, GT;
vector<set<int>> ctc;
stack<int> order;

void ReadInput();
void Solve();
void DFS(int node);
void DFST(int node);

int main()
{
	ReadInput();
	Solve();
	
	return 0;
}

void Solve()
{
	for (int node = 1; node <= n; ++node)
		if (!v[node])
			DFS(node);
			
	v = VB(n + 1);
	
	while (!order.empty())
	{
		int node = order.top();
		order.pop();
		if (v[node])
			continue;
			
		currCmp.clear();
		DFST(node);
		
		ctc.push_back(currCmp);
	}
	
	fout << ctc.size() << '\n';
	for (auto c : ctc)
	{
		for (int node : c)
			fout << node << ' ';
		fout << '\n';
	}
}

void DFS(int node)
{
	v[node] = true;
	
	for (int nbr : G[node])
		if (!v[nbr])
			DFS(nbr);
			
	order.push(node);
}

void DFST(int node)
{
	v[node] = true;
	currCmp.insert(node);
	
	for (int nbr : GT[node])
		if (!v[nbr])
			DFST(nbr);
}

void ReadInput()
{
	fin >> n >> m;
	
	v = VB(n + 1);
	G = GT = VVI(n + 1);
	
	int u, v;
	while (m--)
	{
		fin >> u >> v;
		
		G[u].push_back(v);
		GT[v].push_back(u);
	}
}