Pagini recente » Cod sursa (job #3266633) | Cod sursa (job #367146) | Cod sursa (job #55241) | Cod sursa (job #2971875) | Cod sursa (job #1402724)
#include <cstdio>
#include <vector>
#define nmax 100005
using namespace std;
vector<int> g[nmax],sol[nmax];
int n,m,nrc,niv[nmax],vf;
bool viz[nmax];
pair<int,int> st[nmax];
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 solutie(int x,int y)
{
++nrc;
while(st[vf].first!=x&&st[vf].second!=y)
{
sol[nrc].push_back(st[vf].second);
vf--;
}
sol[nrc].push_back(x);
sol[nrc].push_back(y);
vf--;
}
void dfs(int k,int tata,int nivel,int &niv_min)
{
if(viz[k]==1)
niv_min=niv[k];
else
{
viz[k]=1;
niv[k]=nivel;
niv_min=nivel;
int aux;
for(vector<int>::iterator ii=g[k].begin();ii!=g[k].end();++ii)
{
if(*ii!=tata)
{
if(viz[*ii]==1)
dfs(*ii,k,nivel+1,aux);
else
{
st[++vf]=make_pair(k,*ii);
dfs(*ii,k,nivel+1,aux);
if(nivel<=aux)
solutie(k,*ii);
}
if(niv_min>aux)
niv_min=aux;
}
}
}
}
void afisare()
{
printf("%d\n",nrc);
for(int i=1;i<=nrc;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;
}