Pagini recente » Cod sursa (job #2145847) | Cod sursa (job #2178331) | Cod sursa (job #2831256) | Cod sursa (job #1626833) | Cod sursa (job #582382)
Cod sursa(job #582382)
#include <stdio.h>
#define MAX 100001
int size,Sol,N;
int use[MAX],niv[MAX],T[MAX],low[MAX],com[MAX];
struct coord
{
int x,y;
}stack[MAX];
struct graf
{
int nod;
graf *link;
}*G[MAX];
struct vector
{
int nod;
vector *link;
}*v[MAX];
inline void add(int x,int y)
{
vector *p;
p=new vector;
p->nod=y;
p->link=v[x];
v[x]=p;
}
inline void addnod(int x,int y)
{
graf *p;
p=new graf;
p->nod=y;
p->link=G[x];
G[x]=p;
}
inline void insert(int x,int y)
{
stack[++size].x=x;
stack[size].y=y;
}
inline void erase(int &x,int &y)
{
x=stack[size].x;
y=stack[size].y;
size--;
}
inline void df(int nod)
{
graf *p;
int x,y,Xend,Yend,i;
p=G[nod];
use[nod]=1;
low[nod]=niv[nod];
while(p)
{
if(p->nod!=T[nod]&&niv[nod]>niv[p->nod]) insert(p->nod,nod);
if(!use[p->nod])
{
T[p->nod]=nod;
niv[p->nod]=niv[nod]+1;
df(p->nod);
if(low[p->nod]<low[nod]) low[nod]=low[p->nod];
else
if(low[p->nod]>=niv[nod])
{
Xend=nod;
Yend=p->nod;
Sol++;
x=0;
y=0;
for(i=0;i<=N;i++) com[i]=0;
while((x!=Xend||y!=Yend)&&(x!=Yend||y!=Xend))
{
erase(x,y);
if((x!=Xend||y!=Yend)&&(x!=Yend||y!=Xend)&&(!com[x]))
{
add(Sol,x);
com[0]=1;
}
if((x!=Xend||y!=Yend)&&(x!=Yend||y!=Xend)&&(!com[y]))
{
add(Sol,y);
com[0]=1;
}
com[x]=1;
com[y]=1;
}
if(!com[0])
{
add(Sol,x);
add(Sol,y);
}
}
}
else
if(p->nod!=T[nod]&&low[nod]>niv[p->nod]) low[nod]=niv[p->nod];
p=p->link;
}
}
inline void screen(int nod)
{
vector *p;
p=v[nod];
while(p)
{
printf("%d ",p->nod);
p=p->link;
}
}
int main()
{
int M,i,x,y;
freopen("biconex.in","r",stdin);
scanf("%d%d",&N,&M);
for(i=1;i<=M;i++)
{
scanf("%d%d",&x,&y);
addnod(x,y);
addnod(y,x);
}
for(i=1;i<=N;i++)
{
T[i]=0;
use[i]=0;
niv[i]=0;
low[i]=0;
}
for(i=1;i<=N;i++)
if(!use[i])
{
niv[i]=1;
size=1;
df(i);
}
freopen("biconex.out","w",stdout);
printf("%d\n",Sol);
for(i=1;i<=Sol;i++)
{
screen(i);
printf("\n");
}
return 0;
}