Pagini recente » Cod sursa (job #1826058) | Cod sursa (job #1486131) | Cod sursa (job #2684142) | Cod sursa (job #2672792) | Cod sursa (job #382132)
Cod sursa(job #382132)
#include <stdio.h>
#define max 100010
struct lista
{
int nod;
lista *next;
};
int min(int a,int b)
{
if(a>b) return b;
return a;
}
lista *g[max],*sol[max],*p;
int n,m,i,j,preord[max],nivmin[max],t[max],stack[max*2],top,timp,comp;
char s[max];
void push(lista *&i,int j)
{
lista *p=new lista;
p->nod=j;
p->next=i;
i=p;
}
void add(int v,int w)
{
int i,j;
comp++;
do
{
j=stack[top--]; i=stack[top--];
push(sol[comp],i);
push(sol[comp],j);
}
while(i!=v || j!=w);
}
void dfs(int v)
{
int w;
s[v]=1;
preord[v]=nivmin[v]=++timp;
for(lista *p=g[v]; p!=NULL; p=p->next)
{
w=p->nod;
if(!s[w])//tree edge
{
stack[++top]=v;
stack[++top]=w;
t[w]=v;//predecesor
dfs(w);
if(nivmin[w]>=preord[v]) add(v,w);
nivmin[v]=min(nivmin[v],nivmin[w]);
}
else
if(w!=t[v]) nivmin[v]=min(nivmin[v],preord[w]);//back edge
}
}
int main()
{
freopen("biconex.in","r",stdin);
freopen("biconex.out","w",stdout);
scanf("%d%d",&n,&m);
for(; m>0; m--)
{
scanf("%d%d",&i,&j);
push(g[i],j);
push(g[j],i);
}
for(i=1; i<=n; i++)
if(!s[i])
{
timp=0;
dfs(i);
}
printf("%d\n",comp);
for(i=1; i<=comp; i++)
{
for(p=sol[i]; p!=NULL; p=p->next) s[p->nod]=0;
for(p=sol[i]; p!=NULL; p=p->next)
{
if(!s[p->nod])
{
s[p->nod]=1;
printf("%d ",p->nod);
}
}
printf("\n");
}
return 0;
}