Pagini recente » Cod sursa (job #297873) | Cod sursa (job #1257611) | Cod sursa (job #2563426) | Cod sursa (job #2427694) | Cod sursa (job #2367198)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int n, m, comp, timp;
vector<int>G[100000], Sol[100000];
int low[100000], disc[100000], TT[100000];
bool viz[100000];
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;
--x; --y;
G[x].push_back(y);
G[y].push_back(x);
}
comp=-1;
DFS(0);
for(int i=0; i<comp; ++i) sort(Sol[i].begin(), Sol[i].end());
fout<<comp+1<<"\n";
for(int i=0; i<comp; ++i)
{
for(auto it:Sol[i]) fout<<it+1<<" ";
fout<<"\n";
}
return 0;
}