#include <fstream>
#include <list>
#include <stack>
#include <queue>
#include <vector>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
class Graf
{
int nrNoduri;
int nrMuchii;
bool orientat;
vector<vector<int>> listaAdiacenta;
public:
Graf(bool o)
{
nrNoduri = 0;
nrMuchii = 0;
orientat = o;
}
Graf(int n, int m, bool o)
{
nrNoduri = n;
nrMuchii = m;
orientat = o;
}
void citireGraf()
{
int x, y;
vector<int> v;
for (int i = 0; i < nrMuchii; i++)
listaAdiacenta.push_back(v);
if (orientat)
{
for (int i = 0; i < nrMuchii; i++)
{
fin >> x >> y;
listaAdiacenta[x].push_back(y);
}
}
else
{
for (int i = 0; i < nrMuchii; i++)
{
fin >> x >> y;
listaAdiacenta[x].push_back(y);
listaAdiacenta[y].push_back(x);
}
}
}
void afisareGraf()
{
fout << "Lista de adiacenta asociata grafului <G>:\n\n\n";
for (int i = 1; i <= nrNoduri; i++)
{
if (listaAdiacenta[i].size() > 0)
{
fout << i << " : ";
for (int x : listaAdiacenta[i])
fout << x << " ";
fout << "\n\n";
}
}
}
vector<vector<int>> componenteConexe()
{
vector<vector<int>> listaCC;
vector<int> componentaConexa;
vector<bool> vizitat(nrNoduri + 1, false);
for (int i = 1; i <= nrNoduri; i++)
if (!vizitat[i])
{
DFS(i, componentaConexa, vizitat);
listaCC.push_back(componentaConexa);
componentaConexa.clear();
}
return listaCC;
}
vector<vector<int>> componenteTareConexe()
{
vector<vector<int>> listaCTC;
vector<int> discOrder(nrNoduri + 1, 0); // nodul x este al discOrder[x]-lea nod obtinut din parcurgerea DFS
vector<int> lowLink(nrNoduri + 1, 0);
vector<bool> onStack(nrNoduri + 1, false);
stack<int> stack; // stiva care valideaza apartenenta unui nod la o componenta conexa
for (int i = 1; i <= nrNoduri; i++)
if (discOrder[i] == 0)
TareConexDFS(i, listaCTC, discOrder, lowLink, stack, onStack);
return listaCTC;
}
vector<vector<int>> componenteBiconexe()
{
vector<vector<int>> listaCBC;
vector<int> adancimi(nrNoduri + 1, 0);
vector<int> lowLink(nrNoduri + 1, 0); // adancimea maxima pe care o poate atinge un nod prin descendenti
vector<bool> vizitat(nrNoduri + 1, false);
stack<int> stack;
BiconexDFS(1, 1, stack, vizitat, adancimi, lowLink, listaCBC);
return listaCBC;
}
void distanteBFS(int nodS)
{
vector<bool> vizitat(nrNoduri + 1, false);
vector<int> distanta(nrNoduri + 1, -1);
BFS(nodS, vizitat, distanta);
for (int i = 1; i <= nrNoduri; i++)
fout << distanta[i] << " ";
}
private:
void DFS(int nodS, vector<int>& componentaConexa, vector<bool>& vizitat)
{
vizitat[nodS] = true;
componentaConexa.push_back(nodS);
for (auto vecin : listaAdiacenta[nodS])
if (!vizitat[vecin])
DFS(vecin, componentaConexa, vizitat);
}
void BFS(int nodS, vector<bool>& vizitat, vector<int>& distanta)
{
queue<int> queue;
queue.push(nodS);
vizitat[nodS] = true;
distanta[nodS] = 0;
while (!queue.empty())
{
int nodCurent = queue.front();
//fout << nodCurent << " ";
queue.pop();
for (auto vecin : listaAdiacenta[nodCurent])
if (!vizitat[vecin])
{
queue.push(vecin);
vizitat[vecin] = true;
distanta[vecin] = distanta[nodCurent] + 1;
}
}
}
void TareConexDFS(int nodS, vector<vector<int>>& listaCTC, vector<int>& discOrder, vector<int>& lowLink, stack<int>& stack, vector<bool>& onStack)
{
static int idCurent = 1;
stack.push(nodS);
onStack[nodS] = true;
discOrder[nodS] = lowLink[nodS] = idCurent++;
for (auto x : listaAdiacenta[nodS])
{
if (discOrder[x] == 0) // daca nodul nu a fost explorat, pornim DFS din el, iar la revenirea din recursie, il incadram intr-o componenta conexa;
{
TareConexDFS(x, listaCTC, discOrder, lowLink, stack, onStack);
lowLink[nodS] = min(lowLink[nodS], lowLink[x]);
}
else // daca nodul a fost explorat si se afla pe stiva de validare, il incadram intr-o componenta conexa;
if (onStack[x])
lowLink[nodS] = min(lowLink[nodS], discOrder[x]);
}
// daca ID - ul nodului corespunde cu lowLink - value - ul sau, inseamna ca nodul este radacina componentei sale conexe,
if (lowLink[nodS] == discOrder[nodS]) // si putem scoate de pe stiva toate nodurile pana la nodS, deoarece am terminat de explorat componenta respectiva;
{
vector<int> componentaConexa;
int top;
do
{
top = stack.top();
stack.pop();
onStack[top] = false;
componentaConexa.push_back(top);
} while (nodS != top);
listaCTC.push_back(componentaConexa);
}
}
void BiconexDFS(int nodS, int adancimeCurenta, stack<int>& stack, vector<bool>& vizitat, vector<int>& adancimi, vector<int>& lowLink, vector<vector<int>>& listaCBC)
{
stack.push(nodS); // stiva retine parcurgerea DFS a subarborilor grafului
vizitat[nodS] = true;
adancimi[nodS] = lowLink[nodS] = adancimeCurenta; // adancimi[x] = nivelul de adancime al nodului X din arborele DFS; lowLink[x] = adancimea minima la care se poate intoarce nodul X;
for (auto x : listaAdiacenta[nodS])
{
if (vizitat[x])
lowLink[nodS] = min(lowLink[nodS], adancimi[x]); // adancimea minima a nodului curent S = min (adancimea sa minima curenta; adancimea vecinilor sai)
else
{
BiconexDFS(x, adancimeCurenta + 1, stack, vizitat, adancimi, lowLink, listaCBC);
lowLink[nodS] = min(lowLink[nodS], lowLink[x]); // la intoarcerea din recursie, nodurile cu adancimea < adancimea nodului pe care s-a facut recursia
// isi minimizeaza adancimea minima lowLink cu a succesorilor;
if (lowLink[x] == adancimi[nodS])
{ // cand ajungem la succesorul radacinii componentei, eliminam nodurile pana la radacina din stiva, formand o componenta biconexa;
vector<int> componentaBiconexa;
int top;
do
{
top = stack.top();
stack.pop();
componentaBiconexa.push_back(top);
} while (x != top);
componentaBiconexa.push_back(nodS);
listaCBC.push_back(componentaBiconexa);
}
}
}
}
};
int main()
{
int n, m, s;
fin >> n >> m;
Graf G(n, m, false);
//Graf G(false);
G.citireGraf();
//G.afisareGraf();
/* ---> COMPONENTE BICONEXE <--- */
vector<vector<int>> CBC = G.componenteBiconexe();
fout << CBC.size() << "\n";
for (int i = 0; i < CBC.size(); i++)
{
for (auto x : CBC[i])
fout << x << " ";
fout << "\n";
}
}