Pagini recente » Cod sursa (job #486090) | Cod sursa (job #103158) | Cod sursa (job #2680861) | Cod sursa (job #2930850) | Cod sursa (job #3166752)
#include <fstream>
#include <vector>
using namespace std;
ifstream cin ("biconex.in");
ofstream cout ("biconex.out");
vector <int> adiacenta[100001];
vector < vector <int> > componente;
int nivel[100001] , minim_accesibil[1001] , parcurse[100001] , numar_componente;
void Parcurgere (const int nod_actual , const int nod_sursa)
{
parcurse[++parcurse[0]] = nod_actual;
minim_accesibil[nod_actual] = nivel[nod_actual] = nivel[nod_sursa] + 1;
for (auto nod_vecin : adiacenta[nod_actual]) {
if (nod_vecin != nod_sursa)
{
if (!nivel[nod_vecin])
{
Parcurgere(nod_vecin , nod_actual);
minim_accesibil[nod_actual] = min(minim_accesibil[nod_actual] , minim_accesibil[nod_vecin]);
if (nivel[nod_actual] <= minim_accesibil[nod_vecin])
{
componente.resize(numar_componente + 1);
while (parcurse[parcurse[0]] != nod_actual)
{ componente[numar_componente].push_back(parcurse[parcurse[0]--]); }
componente[numar_componente++].push_back(nod_actual);
}
}
else { minim_accesibil[nod_actual] = min(minim_accesibil[nod_actual] , nivel[nod_vecin]); }
}
}
}
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 nod_actual = 1 ; nod_actual <= numar_noduri ; nod_actual++) {
if (!nivel[nod_actual]) { Parcurgere(nod_actual , 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;
}