Cod sursa(job #2312932)

Utilizator dey44andIoja Andrei-Iosif dey44and Data 5 ianuarie 2019 19:55:48
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.55 kb
#include <fstream>
#include <vector>
#include <stack>

#define input "ctc.in"
#define output "ctc.out"
#define NMAX 100005

using namespace std;

ifstream in(input);
ofstream out(output);

vector < int > muchii[NMAX], muchii_gt[NMAX], componente[NMAX];
stack < int > postpone;

int noduri, muchi, ctc, uz[NMAX];

void Read_Data()
{
	in >> noduri >> muchi;
	for (int i = 1; i <= muchi; i++)
	{
		int x, y;
		in >> x >> y;
		muchii[x].push_back(y);
		muchii_gt[y].push_back(x);
	}
}

void DFS_original(int nod)
{
	uz[nod] = 1;
	for (unsigned i = 0; i < muchii[nod].size(); i++)
	{
		int new_nod = muchii[nod][i];
		if (!uz[new_nod]) DFS_original(new_nod);
	}
	postpone.push(nod);
}

void DFS_made_in_china(int nod)
{
	componente[ctc].push_back(nod);
	uz[nod] = 0;
	for (unsigned i = 0; i < muchii_gt[nod].size(); i++)
	{
		int new_nod = muchii_gt[nod][i];
		if (uz[new_nod]) DFS_made_in_china(new_nod);
	}
}

void Solve_Cerinta_Jupanului()
{
	// Parcurgem graful in adancime
	for (int i = 1; i <= noduri; i++)
	if (!uz[i]) DFS_original(i);
	// Determinam componentele conexe pe mafii
	while (!postpone.empty())
	{
		int nod = postpone.top();
		if (uz[nod])
		{
			ctc++;
			DFS_made_in_china(nod);
		}
		postpone.pop();
	}
	// Afisam capului di tuti capi ce am aflat
	out << ctc << "\n";
	for (int i = 1; i <= ctc; i++)
	{
		for (unsigned j = 0; j < componente[i].size(); j++)
			out << componente[i][j] << " ";
		out << "\n";
	}
}

int main()
{
	Read_Data();
	Solve_Cerinta_Jupanului();
	return 0;
}