Pagini recente » Cod sursa (job #53832) | Cod sursa (job #1134870) | Cod sursa (job #1414552) | Cod sursa (job #3258694) | Cod sursa (job #1414175)
#include <cstdio>
#include <stack>
#include <vector>
#define nmax 100005
using namespace std;
int n,m,nivel[nmax],nr;
vector<int> g[nmax],sol[nmax];
stack<pair<int,int> >st;
bool viz[nmax];
void solutie(int x,int y)
{
++nr;
int xx=st.top().first;
int yy=st.top().second;
while(xx!=x&&yy!=y)
{
st.pop();
sol[nr].push_back(yy);
xx=st.top().first;
yy=st.top().second;
}
sol[nr].push_back(xx);
sol[nr].push_back(xx);
st.pop();
}
void dfs(int k,int tata,int niv,int &niv_min)
{
if(viz[k])
niv_min=nivel[k];
else
{
int aux;
niv_min=niv;
nivel[k]=niv;
viz[k]=1;
for(vector<int>::iterator ii=g[k].begin();ii!=g[k].end();++ii)
if(*ii!=tata)
{
if(viz[*ii])
dfs(*ii,k,niv+1,aux);
else
{
st.push(make_pair(k,*ii));
dfs(*ii,k,niv+1,aux);
if(aux>=niv)
solutie(k,*ii);
}
if(aux<niv_min)
niv_min=aux;
}
}
}
void citire()
{
int x,y;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
g[x].push_back(y);
g[y].push_back(x);
}
}
void afisare()
{
printf("%d\n",nr);
for(int i=1;i<=nr;i++)
{
for(vector<int>::iterator ii=sol[i].begin();ii!=sol[i].end();++ii)
printf("%d ",*ii);
printf("\n");
}
}
int main()
{
freopen("biconex.in","r",stdin);
freopen("biconex.out","w",stdout);
citire();
int aux;
dfs(1,-1,1,aux);
afisare();
return 0;
}