Cod sursa(job #2515790)

Utilizator alex2209alexPavel Alexandru alex2209alex Data 29 decembrie 2019 15:48:56
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.41 kb
#include <bits/stdc++.h>

using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
//---------------------------------------
///Globale
int n,T[100001],ap[100001],rasp,stiva[100001],nr;
vector<int>muchii[100001],raspuns[100001];
//---------------------------------------
///Functii
void citire();
void rezolvare();
void afisare();
//---------------------------------------
int main()
{
	citire();
	rezolvare();
	afisare();
}
//---------------------------------------
void afisare()
{
	g << rasp << '\n';
	while(rasp)
	{
		for(auto nod : raspuns[rasp])
			g << nod << ' ';
		g << '\n';
		rasp--;
	}
}
//---------------------------------------
void dfs(int nod)
{
	stiva[++nr] = nod;
	for(auto dest : muchii[nod])
		if(ap[dest])
			ap[nod] = min(ap[nod],T[dest]);
		else
		{
			int poz = nr;
			ap[dest] = T[dest] = T[nod] + 1;
			dfs(dest);
			ap[nod] = min(ap[nod],ap[dest]);
			if(ap[dest] >= T[nod])
			{
				raspuns[++rasp].push_back(nod);
				while(poz < nr)
                    raspuns[rasp].push_back(stiva[nr--]);
			}
		}
}
//---------------------------------------
void rezolvare()
{
	T[1] = ap[1] = 1;
	dfs(1);
}
//---------------------------------------
void citire()
{
	ios_base::sync_with_stdio(false);
	int m;
	f >> n >> m;
	while(m--)
	{
		int x,y;
		f >> x >> y;
		muchii[x].push_back(y);
		muchii[y].push_back(x);
	}
	f.close();
}