Cod sursa(job #2958668)

Utilizator alin_simpluAlin Pop alin_simplu Data 27 decembrie 2022 17:44:27
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.52 kb
#include <fstream>
#include <set>
#include <vector>
#include <stack>
using namespace std;

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

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

VVI G;
VB V, inStack;
SI C;     // comp. curenta
SSI CTC;  //
VI index, low;
int idx;
stack<int> stk;

int n, m;

void ReadData();
void Tarjan();
void Extract_CBC(int x);
void Print_CBC();

int main(){
	ReadData();
	Tarjan();
	Print_CBC();
	
	return 0;
}

void Print_CBC(){
	fout << CTC.size() << '\n';
	
	for (auto const& comp : CTC){
		for (auto const& node : comp)
		     fout << node << ' ';
		fout << '\n';
		}
}

void Extract_CBC(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;
	index[x] = low[x] = ++idx;
	stk.emplace(x);
	inStack[x] = true;
	
	for (auto const& y : G[x])
		if (!V[y]){   // daca y este fiul lui x;
			DF(y);
			low[x] = min(low[x], low[y]);
		}
		else
		    if(inStack[y])  // daca y este stramos al lui x
		    low[x] = min(low[x], index[y]);
		
	if (index[x] == low[x]){ // daca x este tatal unei noi C.T.C.
		Extract_CBC(x);
	}
}

void Tarjan(){
	for (int node = 1; node <= n; ++node){
		if (!V[node])
		    DF(node);
	}
}
   
void ReadData(){
	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].emplace_back(y);
	}
}