Cod sursa(job #2958669)

Utilizator alin_simpluAlin Pop alin_simplu Data 27 decembrie 2022 17:45:17
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.85 kb
/* Componentele tare-conexe (G.O.)
 * Algoritmul lui Tarjan
 * Complexitate:
 * 
 * 	O(m)   ca timp de executare
 *  O(m)   ca spatiu de memorie ocupat
 */ 
#include <fstream>
#include <vector>
#include <stack>
using namespace std;

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

using VI  = vector<int>;
using VVI = vector<VI>;
using VB  = vector<bool>;

VVI G;
VB  v;          // marcam nodurile vizitate
VB inStack;     // marcam nodurile din stiva
VVI ctc;        // retine pe fiecare linie cate o comp tare conexa
VI c;           // comp tare conexa curenta
stack<int> stk; // retine nodurile in ordinea descoperirii acestora
VI index, low;  // indexul si indexul minim pt fiecare nod
int idx;

int n, m;

void CitesteGraf();
void Tarjan();
void Df(int x);    
void ScrieCTC();

int main()
{
	CitesteGraf();
	Tarjan();
	ScrieCTC();
	
	return 0;
}

void Tarjan()
{
	for (int node = 1; node <= n; ++node)
		if (!v[node])
			Df(node);
}

void Df(int x)
{
	v[x] = true;
	index[x] = low[x] = ++idx;
	stk.push(x);
	inStack[x] = true;
	
	for (int const& y : G[x])
		if (!v[y])   // y este fiul lui x
		{
			Df(y);
			low[x] = min(low[x], low[y]);
		}
		else // daca 
			if (inStack[y]) // daca y este stramos al lui x (adica x->y = muchie de intoarcere)
				low[x] = min(low[x], index[y]);
				
	if (index[x] == low[x]) // x este repreentanul unei noi comp. t-c
	{
		c.clear();
		while (!stk.empty())
		{
			int node = stk.top();
			stk.pop();
			inStack[node] = false;
			c.push_back(node);
			if (node == x)
				break;
		}
		
		ctc.push_back(c);
	}
}


void CitesteGraf()
{
	fin >> n >> m;
	G = VVI(n + 1);
	v = VB(n + 1);
	index = low = VI(n + 1);
	inStack = VB(n + 1);
	int x, y;
	while (m--)
	{
		fin >> x >> y;
		G[x].push_back(y);
	}
}

void ScrieCTC()
{
	fout << ctc.size() << '\n';
	for (auto const&C : ctc)
	{
		for (const int& node : C)
			fout << node << ' ';
		fout << '\n';
	}
}