Cod sursa(job #2889868)

Utilizator BalutaBaluta Iustinian-Lucian Baluta Data 13 aprilie 2022 16:27:47
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.51 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>



using namespace std;

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

#define NMAX 100005                                                                                                                                                       //All right reverved by Baluta!!!

vector <int> G[NMAX];
vector <int> GT[NMAX];
vector <int> Result[NMAX];

stack <int> S;

int Color[NMAX];

int N, M, CompConexe;

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

void DFS(int nod) {
	Color[nod] = 1;
	for (unsigned int y = 0; y < G[nod].size(); y++)
	{
		int Vecin = G[nod][y];
		if (!Color[Vecin])
			DFS(Vecin);
	}
	S.push(nod);
}

void DFS_T(int nod) {
	Color[nod] = 2;
	Result[CompConexe].push_back(nod);

	for (unsigned int y = 0; y < GT[nod].size(); y++)
	{
		int Vecin = GT[nod][y];
		if (Color[Vecin] == 1)
			DFS_T(Vecin);
	}
}

void Solve()
{
	for (int i = 1; i <= N; i++)
		if (!Color[i])
			DFS(i);

	while (!S.empty())
	{
		int nod = S.top();
		if (Color[nod] == 1)
		{
			CompConexe++;
			DFS_T(nod);
		}
		S.pop();
	}
}

void Print()
{
	fout << CompConexe << "\n";
	for (unsigned int x = 1; x <= CompConexe; x++)
	{
		for (unsigned int y = 0; y < Result[x].size(); y++)
			fout << Result[x][y] << " ";
		fout << "\n";
	}
}

int main()
{
	Citire();
	Solve();
	Print();
}