Cod sursa(job #3196277)

Utilizator PieleVoinescu David Piele Data 23 ianuarie 2024 13:21:01
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.67 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <stack>

const int NMAX = 100001;
const int INF = 1e9;

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

int N, M, Start;
std::vector<int>G[NMAX];
std::vector<int>GT[NMAX];
std::stack<int>Sortare_Topologica;
int Viz[NMAX], Viz2[NMAX];
int Dist[NMAX];
int Tata[NMAX];
bool Possible = true;
int eStiva[NMAX];
std::vector<int>Componente_Tare[NMAX];

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

void Dfs(int nod)
{
	Viz[nod] = 1;
	eStiva[nod] = true;
	for (auto& x : G[nod])
	{
		if (!Viz[x])
			Dfs(x);
	}
	eStiva[nod] = false;
	Sortare_Topologica.push(nod);
}

void Dfs2(int nod, int tura)
{
	Viz2[nod] = 1;
	Componente_Tare[tura].push_back(nod);
	for (auto& x : GT[nod])
	{
		 if (!Viz2[x])
			Dfs2(x, tura);
	}
}

void Sortez()
{
	for (int i = 1; i <= N; ++i)
	{
		if (!Viz[i])
			Dfs(i);
	}
	int comp_tare = 1;
	while (!Sortare_Topologica.empty())
	{
		int nod = Sortare_Topologica.top();
		Sortare_Topologica.pop();
		if (!Viz2[nod])
		{
			Dfs2(nod, comp_tare);
			comp_tare++;
		}
	}
	fout << comp_tare - 1 << '\n';
	for (int i = 1; i < comp_tare; ++i)
	{
		for (auto& x : Componente_Tare[i])
			fout << x << " ";
		fout << '\n';
	}
}

void Afisare()
{
	if (!Possible)
		std::cout << "IMPOSSIBLE";
	else
	{
		int ordine = 1;
		while (!Sortare_Topologica.empty())
		{
			fout << Sortare_Topologica.top() << " ";
			Sortare_Topologica.pop();
		}
	}
}

int main()
{
	Citire();
	Sortez();
	//Afisare();
}