Pagini recente » Cod sursa (job #1598899) | Cod sursa (job #2580259) | Cod sursa (job #436807) | Cod sursa (job #833958) | Cod sursa (job #3188117)
#include <fstream>
#include <vector>
using namespace std;
ifstream cin ("biconex.in");
ofstream cout ("biconex.out");
vector <int> adiacenta[100001];
vector < vector <int> > componente;
int vizitat[100001] , minim_accesibil[100001] , moment[100001];
bool in_stiva[100001];
void Parcurgere (const int nod_actual , const int nod_sursa)
{
in_stiva[nod_actual] = true;
vizitat[++vizitat[0]] = nod_actual;
minim_accesibil[nod_actual] = moment[nod_actual] = ++moment[0];
for (auto nod_vecin : adiacenta[nod_actual]) {
if (nod_vecin != nod_sursa) {
if (in_stiva[nod_vecin])
{ minim_accesibil[nod_actual] = min(minim_accesibil[nod_actual] , moment[nod_vecin]); }
else if (!moment[nod_vecin])
{
Parcurgere(nod_vecin , nod_actual);
if (minim_accesibil[nod_vecin] < minim_accesibil[nod_actual])
{ minim_accesibil[nod_actual] = minim_accesibil[nod_vecin]; }
else
{
const int indice = componente.size();
componente.resize(indice + 1);
while (in_stiva[nod_vecin]) {
componente[indice].push_back(vizitat[vizitat[0]]);
in_stiva[vizitat[vizitat[0]--]] = false;
}
componente[indice].push_back(nod_actual);
}
}
}
}
}
int main ()
{
int numar_noduri , numar_muchii;
cin >> numar_noduri >> numar_muchii;
for (int nod[2] ; numar_muchii-- ; ) {
cin >> nod[0] >> nod[1];
adiacenta[nod[0]].push_back(nod[1]);
adiacenta[nod[1]].push_back(nod[0]);
}
for (int indice = 1 ; indice <= numar_noduri ; indice++)
{ if (!moment[indice]) { Parcurgere(indice , 0); } }
cout << componente.size() << '\n';
for (auto componenta : componente) {
for (auto nod_actual : componenta)
{ cout << nod_actual << ' '; }
cout << '\n';
}
cout.close(); cin.close();
return 0;
}