Pagini recente » Cod sursa (job #156253) | Cod sursa (job #1361995) | Cod sursa (job #2071670) | Cod sursa (job #1568267) | Cod sursa (job #394986)
Cod sursa(job #394986)
using namespace std;
#include<fstream>
ofstream fout("biconex.in");
struct nod
{
int vf;
nod* next;
};
struct muchie
{
int i;
int j;
};
int n,m,y,vs,*v,*viz,*componenta[100005],*h;
nod *G[100005];
muchie *stiva;
void addarc(int,int);
int dfs(int,int,int);
void comp(int,int);
int main()
{
int i,x,d;
ifstream fin("biconex.out");
fin>>n>>m;
for(i=1;i<=m;++i)
{
fin>>x>>y;
addarc(x,y);
addarc(y,x);
}
v=new int[n+1];
h=new int[n+1];
for(i=0;i<=n;++i)
v[i]=h[i]=0;
stiva=new muchie[m+1];
viz=new int[n+1];
y=0;
x=dfs(1,0,1);
fout<<y<<'\n';
for(i=1;i<=y;++i)
{
d=componenta[i][0];
for(x=1;x<=d;++x)
fout<<componenta[i][x]<<' ';
fout<<'\n';
}
return 0;
}
void addarc(int i,int j)
{
nod *p=new nod;
p->vf=j;
p->next=G[i];
G[i]=p;
}
int dfs(int k,int t,int niv)
{
int niv_min,aux;
nod *p;
if(v[k])
return h[k];
else
{
v[k]=1;
h[k]=niv_min=niv;
for(p=G[k];p;p=p->next)
if(p->vf!=t)
if(v[p->vf]==0 || h[p->vf]<niv)
{
stiva[++vs].i=p->vf;
stiva[vs].j=k;
if(v[p->vf])
aux=dfs(p->vf,k,niv+1);
else
{
aux=dfs(p->vf,k,niv+1);
if(niv<=aux)
comp(p->vf,k);
}
if(aux<niv_min)
niv_min=aux;
}
}
return niv_min;
}
void comp(int i,int j)
{
int x;
muchie m;
componenta[++y]=new int[n+1];
for(x=1;x<=n;++x)
viz[x]=0;
x=0;
do{
m=stiva[vs--];
if(viz[m.i]==0)
{
componenta[y][++x]=m.i;
viz[m.i]=1;
}
if(viz[m.j]==0)
{
componenta[y][++x]=m.j;
viz[m.j]=1;
}
}while(m.i != i || m.j != j);
componenta[y][0]=x;
}