Pagini recente » Cod sursa (job #1795637) | Cod sursa (job #967353) | Cod sursa (job #1091918) | Cod sursa (job #819589) | Cod sursa (job #2572717)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("biconexe.in");
ofstream fout("biconexe.out");
int n, m, timp, biconex;
vector<int>G[100001], SOL[100001];
bool viz[100001];
int h[100001], low[100001], TT[100001];
stack<pair<int, int>>ST;
void DFS(int nod)
{
viz[nod] = 1;
h[nod] = low[nod] = ++timp;
int children = 0;
for(auto it: G[nod])
{
if(!viz[it])
{
ST.push(make_pair(nod, it));
TT[it] = nod;
++children;
DFS(it);
low[nod] = min(low[nod], low[it]);
if((low[it] >= h[nod]) || (children > 1))
{
++biconex;
int a, b;
do
{
a = ST.top().first;
b = ST.top().second;
ST.pop();
SOL[biconex].push_back(b);
}while(a != nod && b != it);
SOL[biconex].push_back(a);
}
}
else if(it != TT[nod]) low[nod] = min(h[it], low[nod]);
}
}
int main()
{
fin >> n >> m;
for(int i = 1; i <= m; ++i)
{
int x, y;
fin >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
//TT[1] = -1;
DFS(1);
fout << biconex << "\n";
for(int i = 1; i <= biconex; ++i)
{
sort(SOL[i].begin(), SOL[i].end());
for(auto it: SOL[i]) fout << it << " ";
fout << "\n";
}
return 0;
}