Cod sursa(job #3030719)

Utilizator Vincent47David Malutan Vincent47 Data 17 martie 2023 20:29:18
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.48 kb
#include <fstream>
#include <vector>
#include <fstream>
#include <set>
#include <stack>
using namespace std;

using SI   = set<int>;
using SSI  = set<SI>;
using VI   = vector<int>;
using VVI  = vector<VI>;
using VB   = vector<bool>;

ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m;
VVI G;
VI index;
VI low;
int idx;

VB v;
SSI ctc;
SI  c;
stack<int> stk;
vector<bool> inStack;

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

int main()
{
	CitesteGraf();
	Tarjan();
	ScrieCTC();

	return 0;
}

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

void ExtractCC(int x)
{
	c.clear();
	while (!stk.empty())
	{
		int node = stk.top();
		stk.pop();
		inStack[node] = false;
		c.insert(node);
		if (node == x)
			break;
	}

	ctc.insert(c);
}

void Df(int x)
{
	v[x] = true;
	stk.push(x);
	inStack[x] = true;
	index[x] = low[x] = ++idx;

	for (int const& y : G[x])
		if (!v[y])
		{
			Df(y);
			low[x] = min(low[x], low[y]);
		}
		else
			if (inStack[y])
				low[x] = min(low[x], index[y]);

	if (index[x] == low[x])
		ExtractCC(x);
}

void ScrieCTC()
{
	fout << ctc.size() << '\n';

	for (auto cc : ctc)
	{
		for (int x : cc)
			fout << x << ' ';
		fout << '\n';
	}
}

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