Cod sursa(job #2087481)

Utilizator PaulTPaul Tirlisan PaulT Data 13 decembrie 2017 18:42:13
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 kb
// Det Comp. Tare Conexe 
// Alg. lui Tarjan O(m)
#include <fstream>
#include <algorithm>
#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;        // graful,
VI niv, L;    // nivel, niv minim 
VVI cc;      // componentele tare conexe
VI c;         // componenta tare conexa curenta
int cnt;
int nv, tp;
stack<int> stk;
vector<bool> inStack;
int n, m;

void ReadGraph();
void Tarjan(int x);
void Write();

int main()
{
	ReadGraph();
	for (int x = 1; x <= n; ++x)
		if (!niv[x])
			nv = 0, Tarjan(x);
	Write();
}


void Tarjan(int x)
{
	niv[x] = L[x] = ++nv;
	stk.push(x); inStack[x] = true;
	
	for (const int& y : G[x])
		if (!niv[y])    // tree edge
		{
			Tarjan(y);
			L[x] = min(L[x], L[y]);
		}
		else
			if (inStack[y]) // daca y e in stiva, atunci e stramosul lui x 
				L[x] = min(L[x], niv[y]);
				
	if (L[x] == niv[x])
	{
		c.clear();
		while (!stk.empty())
		{
			tp = stk.top();
			stk.pop();
			inStack[tp] = false;
			c.push_back(tp);
			if (tp == x)
				break;
		}
		cc.push_back(c);
	}
}


void Write()
{
	fout << cc.size() << '\n';
	
	for (auto& c : cc)
	{
		for (const int& x : c)
			fout << x << ' ';
		fout << '\n';
	}
}

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