Pagini recente » Cod sursa (job #3339563) | Cod sursa (job #3310255) | Borderou de evaluare (job #3332141) | Cod sursa (job #3313780) | Cod sursa (job #3322010)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream f ("biconex.in");
ofstream g ("biconex.out");
const int NMAX = 100000;
int N, M, nrCB, Niv[NMAX+1], Nma[NMAX+1];
bool viz[NMAX+1];
vector <int> G[NMAX+1], CB[NMAX+1];
stack<int> S;
void citire() {
f >> N >> M;
//
int x, y;
for (int i=1; i<=M; i++) {
f >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
}
void DFS(int nod, int tata) {
S.push(nod);
viz[nod] = 1;
Niv[nod] = Niv[tata] + 1;
Nma[nod] = Niv[nod];
//
for (const auto &x : G[nod]) {
if (x == tata) continue;
//
if (viz[x]) Nma[nod] = min(Nma[nod], Niv[x]);
else {
DFS(x, nod);
Nma[nod] = min(Nma[nod], Nma[x]);
//
if (Nma[x] >= Niv[nod]) {
nrCB++;
while(S.top() != nod) {
CB[nrCB].push_back(S.top());
S.pop();
}
CB[nrCB].push_back(nod);
}
}
}
}
void afisare() {
g << nrCB << '\n';
for (int i=1; i<=nrCB; i++) {
for (const auto &x : CB[i])
g << x << ' ';
g << '\n';
}
}
int main(){
citire();
DFS(1, 0);
afisare();
return 0;
}