Cod sursa(job #2542424)

Utilizator misha1254Mihai Stefanuti misha1254 Data 9 februarie 2020 23:01:23
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.19 kb
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;

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

VVI G, GT;
VB v;
stack<int> stk;

VI c;
VVI ctc;

int n, m;

void CitesteGraf();
void Kosaraju();
void Df(int x);
void DfT(int x);
void AfiseazaCTC();

int main()
{
	CitesteGraf();
	Kosaraju();
	AfiseazaCTC();
}

void CitesteGraf()
{
	cin >> n >> m;
	G = GT = VVI(n + 1);
	v = VB(n + 1);
	int x, y;
	for (int i = 1; i <= m; ++i)
	{
		cin >> x >> y;
		G[x].emplace_back(y);
		GT[y].emplace_back(x);
	}
}

void Kosaraju()
{
	for (int x = 1; x <= n; ++x)
		if ( !v[x] )
			Df(x);
			
	v.assign(n + 1, false);
	
	int x;
	while(!stk.empty())
	{
		x = stk.top();
		stk.pop();
		if ( v[x] ) 	continue;
		c.clear();
		DfT(x);
		ctc.emplace_back(c);
	}
}

void Df(int x)
{
	v[x] = true;
	for (const int y : G[x])
	{
		if (v[y])
			continue;
		DfT(y);
	}
	stk.push(x);
}

void DfT(int x)
{
	v[x] = true;
	c.emplace_back(x);
	
	for (const int &y : GT[x])
	{
		if (v[y])
			continue;
		DfT(y);
	}
}

void AfiseazaCTC()
{
	cout << ctc.size() << '\n';
	
	for (const auto& comp : ctc)
	{
		for (const int& x : comp)
			cout << x << ' ';
		cout << '\n';
	}
}