/*
Am construit graful neorientat folosind liste de adiacență, apoi am aplicat algoritmul Tarjan cu DFS pentru determinarea componentelor biconexe.
Am utilizat vectorii nivel și low pentru a reține nivelul fiecărui nod în arborele DFS și cel mai mic nivel la care se poate ajunge din subarborele său.
Am folosit o stivă în care am memorat muchiile parcurse, iar atunci când condiția low[vecin] >= nivel[nod] a fost îndeplinită, am extras muchiile corespunzătoare unei componente biconexe și am reținut nodurile acesteia, eliminând duplicatele.
La final, am afișat numărul componentelor biconexe și nodurile fiecărei componente.
Complexitate:O(N + M * log M)
*/
#include <fstream>
#include <vector>
#include <stack>
#include <utility>
#include <algorithm>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
vector<int> graf[100001];
bool vizitat[100001];
int nivel[100001], low[100001];
stack<pair<int,int>> st;
vector<vector<int>> componente;
void DFS(int nod, int tata) {
vizitat[nod]=true;
low[nod]=nivel[nod];
for (auto vecin : graf[nod]) {
if (!vizitat[vecin]) {
st.push({nod,vecin});
nivel[vecin] = nivel[nod] + 1;
DFS(vecin,nod);
low[nod]= min(low[nod],low[vecin]);
if (low[vecin]>=nivel[nod]) {
vector<int> comp;
while (true) {
auto muchie=st.top();
st.pop();
comp.push_back(muchie.first);
comp.push_back(muchie.second);
if (muchie.first==nod && muchie.second==vecin)
break;
}
sort(comp.begin(), comp.end());
comp.erase(unique(comp.begin(), comp.end()), comp.end());
componente.push_back(comp);
}
} else if (vecin!=tata && nivel[vecin]<nivel[nod]) {
st.push({nod, vecin});
low[nod]=min(low[nod], nivel[vecin]);
}
}
}
int main() {
int n, m,x ,y;
fin>>n>>m;
for (int i=1; i<=m; i++) {
fin>>x>>y;
graf[x].push_back(y);
graf[y].push_back(x);
}
for (int i=1; i<=n; i++) {
if (!vizitat[i]) {
nivel[i]=1;
DFS(i,0);
}
}
fout<<componente.size()<< '\n';
for (auto comp: componente) {
for (auto nod: comp) {
fout<<nod<< " ";
}
fout<< '\n';
}
}