Pagini recente » Cod sursa (job #2237302) | Cod sursa (job #2320152) | Cod sursa (job #1999631) | Cod sursa (job #1916239) | Cod sursa (job #713707)
Cod sursa(job #713707)
#include <cstdio>
#define nd 100005
using namespace std;
struct nod{ int val; nod *urm; }*p[nd],*comp[nd];
int tata[nd],niv[nd],low[nd],k,st[5][nd*2],uz[nd],sol;
int n,m;
bool viz[nd],critic[nd];
void read()
{ int i,x,y;
nod *aux;
freopen("biconex.in","r",stdin); scanf("%d %d\n",&n,&m);
for(i=1;i<=m;++i)
{
scanf("%d %d\n",&x,&y);
aux=new nod; aux->val=y; aux->urm=p[x]; p[x]=aux;
aux=new nod; aux->val=x; aux->urm=p[y]; p[y]=aux;
}
fclose(stdin);
}
inline int min(int x,int y)
{
if(x<y)return x; else return y;
return 0;
}
void del(int x,int y)
{ nod *aux;
++sol; ++k;
do
{
--k;
if(uz[st[0][k]]!=sol){
aux=new nod; aux->val=st[0][k]; aux->urm=comp[sol]; comp[sol]=aux;
uz[st[0][k]]=sol;
}
if(uz[st[1][k]]!=sol)
{
aux=new nod; aux->val=st[1][k]; aux->urm=comp[sol]; comp[sol]=aux;
uz[st[1][k]]=sol;
}
}
while(st[0][k]!=x&&st[1][k]!=y);
--k;
}
void df(int ind)
{ nod *aux;
viz[ind]=1;
for(aux=p[ind];aux!=NULL;aux=aux->urm)
if(aux->val!=tata[ind])
{
if(viz[aux->val]==0)
{
++k; st[0][k]=ind; st[1][k]=aux->val;
tata[aux->val]=ind; low[aux->val]=niv[aux->val]=niv[ind]+1;
df(aux->val);
if(low[aux->val]>=niv[ind])del(ind,aux->val);
low[ind]=min(low[aux->val],low[ind]);
}
else low[ind]=min(low[ind],niv[aux->val]);
}
}
void write()
{ int i;
nod *aux;
freopen("biconex.out","w",stdout); printf("%d\n",sol);
for(i=1;i<=sol;++i)
{
for(aux=comp[i];aux!=NULL;aux=aux->urm)
printf("%d ",aux->val);
printf("\n");
}
fclose(stdout);
}
int main()
{
read();
niv[1]=1;
low[1]=0;
sol=0;
df(1);
write();
return 0;
}