Pagini recente » Cod sursa (job #2873774) | Cod sursa (job #394655) | Cod sursa (job #2358035) | Cod sursa (job #188807) | Cod sursa (job #582663)
Cod sursa(job #582663)
#include <cstdio>
#include <cstring>
#include <fstream>
#include <vector>
#define Nmx 100002
using namespace std;
int n,m,lvl[Nmx],c[Nmx],nr,nrs,viz[Nmx];
vector <int> sol[Nmx];
struct dat
{ int x,y;}A[Nmx*3];
struct nod
{
int inf;
nod *urm;
};
nod *G[Nmx];
ifstream fin("biconex.in");
void add(int x,int y)
{
nod *aux=new nod;
aux->inf = y;
aux->urm = G[x];
G[x] = aux;
}
void read()
{
int x,y;
fin>>n>>m;
for(int i=1;i<=m;++i)
{
fin>>x>>y;
add(x,y);
add(y,x);
}
}
void baga(int x,int y)
{
int px,py;
++nrs;
do
{
px=A[nr].x;
py=A[nr--].y;
sol[nrs].push_back(py);
}while(px!=x||py!=y);
sol[nrs].push_back(x);
}
void dfs(int nd,int tata)
{
lvl[nd]=lvl[tata]+1;
c[nd]=lvl[nd];
viz[nd]=1;
for(nod *p=G[nd];p;p=p->urm)
{
int x=p->inf;
if(!viz[x])
{
A[++nr].x=nd;
A[nr].y=x;
dfs(x,nd);
if(c[x]<c[nd])
c[nd]=c[x];
if(c[x]>=lvl[nd])
baga(nd,x);
}
else if(tata!=x&&c[x]<c[nd])
c[nd]=c[x];
}
}
int main()
{
freopen("biconex.out","w",stdout);
read();
dfs(1,0);
printf("%d\n",nrs);
for(int i=1;i<=nrs;++i)
{
for(int j=0;j<sol[i].size();++j)
printf("%d ",sol[i][j]);
printf("\n");
}
return 0;
}