Pagini recente » Cod sursa (job #527822) | Cod sursa (job #2678579) | Cod sursa (job #2151494) | Cod sursa (job #3001833) | Cod sursa (job #2367194)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int n, m, comp, timp;
vector<int>G[100001], Sol[100001];
int low[100001], disc[100001], TT[100001];
bool viz[100001];
stack<pair<int, int>>ST;
void DFS(int nod)
{
int children=0;
viz[nod]=1;
low[nod]=disc[nod]=++timp;
for(auto it:G[nod])
{
if(!viz[it])
{
++children;
ST.push(make_pair(nod, it));
TT[it]=nod;
DFS(it);
low[nod]=min(low[nod], low[it]);
if((TT[nod]==-1 && children>=2) || (TT[nod]!=-1 && low[it]>=disc[nod]))
{
int a, b;
++comp;
do
{
a=ST.top().first;
b=ST.top().second;
Sol[comp].push_back(b);
ST.pop();
}while(a!=nod && b!=it);
Sol[comp].push_back(a);
}
}
else if(TT[nod]!=it) low[nod]=min(low[nod], disc[it]);
}
}
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);
}
DFS(1);
for(int i=1; i<=comp; ++i) sort(Sol[i].begin(), Sol[i].end());
fout<<comp<<"\n";
for(int i=1; i<=comp; ++i)
{
for(auto it:Sol[i]) fout<<it<<" ";
fout<<"\n";
}
return 0;
}