Pagini recente » Cod sursa (job #1440604) | Cod sursa (job #782104) | Cod sursa (job #2960729) | Cod sursa (job #1549847) | Cod sursa (job #1642694)
#include <iostream>
#include <fstream>
#include <stdlib.h>
#define nmax 100099
using namespace std;
long *g[nmax];
long sx[nmax],st[nmax],dfn[nmax],low[nmax];
long to,num,n,vf;
long *re[nmax];
ifstream fin("biconex.in");
ofstream fout("biconex.out");
void citire()
{long i,m,x,y;
fin>>n>>m;
for(i=1;i<=n;i++){g[i]=(long*)realloc(g[i],sizeof(long));g[i][0]=0;}
for(i=1;i<=m;i++)
{fin>>x>>y;
g[x][0]++;g[x]=(long*)realloc(g[x],(g[x][0]+1)*sizeof(long));
g[x][g[x][0]]=y;
g[y][0]++;g[y]=(long*)realloc(g[y],(g[y][0]+1)*sizeof(long));
g[y][g[y][0]]=x;
}
}
void afisare(long u,long tu)
{long x,y,cont=0;
cont=0;
to++;
re[to]=(long*)realloc(re[to],sizeof(long));
re[to][0]=0;
do{x=sx[vf]; y=st[vf]; vf--;
re[to][0]++;
re[to]=(long*)realloc(re[to],sizeof(long)*(re[to][0]+1));
re[to][re[to][0]]=x;
}while(x!=u || y!=tu);
if(re[to][0]==1){
re[to][0]++;
re[to]=(long*)realloc(re[to],sizeof(long)*(re[to][0]+1));
re[to][re[to][0]]=y;
}
}
void initializare()
{for(long i=1;i<=n;i++)dfn[i]=-1;
vf=0;
sx[vf]=1;st[vf]=-1;
}
void biconex(long u,long tu)
{long i,x;
//cout<<u<<' '<<tu<<endl;
dfn[u]=low[u]=++num;
for(i=1;i<=g[u][0];i++)
{x=g[u][i];
// cout<<u<<"->"<<x<<endl;
if(x!=tu && dfn[x]<dfn[u])
{sx[++vf]=x; st[vf]=u;
// cout<<"da";
}
if(dfn[x]==-1)
{
biconex(x,u);
low[u]=min(low[x],low[u]);
if(low[x]>=dfn[u])
afisare(x,u);
}else if(x!=tu)low[u]=min(low[u],dfn[x]);
}
}
int main()
{long i,j;
citire();
initializare();
biconex(1,-1);
fout<<to<<'\n';
for(i=1;i<=to;i++)
{for(j=1;j<=re[i][0];j++)fout<<re[i][j]<<' ';
fout<<'\n';}
}