Cod sursa(job #2515333)

Utilizator alex2209alexPavel Alexandru alex2209alex Data 28 decembrie 2019 13:16:43
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.56 kb
#include <bits/stdc++.h>

using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
//-----------------------------------
///Gobale
int n,nr = 1,rasp;
vector<vector<int>>muchii,raspuns;
struct str
{
	int index,low;
	bool ap;
};
vector<str>v;
stack<int>s;
//-----------------------------------
///Functii
void citire();
void rezolvare();
void afisare();
//-----------------------------------
int main()
{
	citire();
	rezolvare();
	afisare();
	return 0;
}
//-----------------------------------
void afisare()
{
	g << rasp << '\n';
	for(int i = 1; i <= rasp; ++i)
	{
		for(auto nod : raspuns[i])
			g << nod << " ";
		g << '\n';
	}
}
//-----------------------------------
void calculeaza_ctc(int nod)
{
	v[nod].index = nr;
	v[nod].low = nr;
	nr++;
	s.push(nod);
	v[nod].ap = 1;
	for(auto dest : muchii[nod])
		if(v[dest].index == 0)
		{
			calculeaza_ctc(dest);
			v[nod].low = min(v[nod].low,v[dest].low);
		}
		else if(v[dest].ap)
			v[nod].low = min(v[nod].low,v[dest].index);
	if(v[nod].low == v[nod].index)
	{
		rasp++;
		raspuns.resize(rasp + 1);
		int x;
		do
		{
		    x = s.top();
		    s.pop();
		    v[x].ap = 0;
			raspuns[rasp].push_back(x);
		}
		while(x != nod);
	}
}
//-----------------------------------
void rezolvare()
{
	for(int i = 1; i <= n; ++i)
		if(v[i].index == 0)
			calculeaza_ctc(i);
}
//-----------------------------------
void citire()
{
	int m;
	f >> n >> m;
	muchii.resize(n + 1);
	v.resize(n + 1);
	while(m--)
	{
		int a,b;
		f >> a >> b;
		muchii[a].push_back(b);
	}
}