Pagini recente » Cod sursa (job #1712393) | Cod sursa (job #1402896) | Cod sursa (job #2130100) | Cod sursa (job #55469) | Cod sursa (job #497039)
Cod sursa(job #497039)
#include <stdio.h>
const int maxn=100001,maxm=200001;
struct nod {
int inf;
nod *next;
} *A[maxn],*Sol[maxn];
struct arc{
int a,b;
} st[maxm];
int i,N,M,NR,index,k,ind[maxn],low[maxn],t[maxn];
void add(int x, int y)
{
nod *q=new nod;
q->inf=y;
q->next=A[x];
A[x]=q;
}
void citire()
{
int x,y;
scanf("%d %d",&N,&M);
for(i=1;i<=M;i++)
{
scanf("%d %d",&x,&y);
add(x,y);
add(y,x);
}
}
int min(int a, int b)
{
if(a<b) return a;
return b;
}
void add_stiva(int x, int y)
{
k++;
st[k].a=x;
st[k].b=y;
}
void adauga_sol(int p)
{
NR++;
while(st[k].a!=p)
{
nod *s=new nod;
s->inf=st[k].b;
s->next=Sol[NR];
Sol[NR]=s;
k--;
}
nod *s=new nod;
s->inf=st[k].b;
s->next=Sol[NR];
Sol[NR]=s;
s=new nod;
s->inf=st[k].a;
s->next=Sol[NR];
Sol[NR]=s;
k--;
}
void dfs(int p)
{
ind[p]=++index;
low[p]=index;
for(nod *x=A[p];x;x=x->next) //verificam vecinii
{
if(x->inf!=t[p]) //daca nu e tatal
{
if(ind[x->inf]==0) //daca nu a fost vizitat inca
{
t[x->inf]=p;
add_stiva(p,x->inf); //adaug muchia in stiva
dfs(x->inf); //il vizitez
low[p]=min(low[p],low[x->inf]);
if(ind[p]<=low[x->inf]) //daca din fii se poate ajunge doar pana la tata sau mai jos
adauga_sol(p);
}
else //update pana unde poate ajunge pe muchia de intoarcere
low[p]=min(low[p],ind[x->inf]);
}
}
}
void afisare()
{
printf("%d\n",NR);
for(i=1;i<=NR;i++)
{
for(nod *x=Sol[i];x;x=x->next)
{
printf("%d ",x->inf);
}
printf("\n");
}
}
int main()
{
freopen("biconex.in","r",stdin);
freopen("biconex.out","w",stdout);
citire();
for(i=1;i<=N;i++) t[i]=-1;
dfs(1);
afisare();
}