Pagini recente » Cod sursa (job #899024) | Statistici Aris Miuta (arismiuta) | Cod sursa (job #480057) | Cod sursa (job #985007) | Cod sursa (job #2169645)
#include <iostream>
#include <fstream>
#define nmax 100000
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
struct nod
{
int info;
bool viz;
nod* urm;
}*v[nmax+5],*c,*e[nmax+5],*sol[nmax+1];
int n,m,disc[nmax+5],low[nmax+5],tata[nmax+5],nrsol=0,time=0,siz=0,st_sol[nmax];
bool viz[nmax+5],mc[nmax+5];
int minv(int a,int b)
{
return a<b?a:b;
}
void add_sol()
{
nrsol++;
sol[nrsol]=new nod;
sol[nrsol]->info=st_sol[1];
sol[nrsol]->viz=0;
sol[nrsol]->urm=0;
nod *d=sol[nrsol];
for(int i=2;i<=siz;i++,d=d->urm)
{
c=new nod;
c->info=st_sol[i];
c->urm=0;
c->viz=0;
d->urm=c;
}
}
void solve(int k)
{
time++;
disc[k]=low[k]=time;
viz[k]=1;
nod *d=v[k];
while(d->urm)
{
d=d->urm;
if(!viz[d->info])
{
tata[d->info]=k;
solve(d->info);
low[k]=minv(low[k],low[d->info]);
if(low[d->info]>disc[k])
{
++nrsol;
sol[nrsol]=new nod;
sol[nrsol]->info=k;
sol[nrsol]->viz=0;
c=new nod;
c->info=d->info;
c->urm=0;
c->viz=0;
sol[nrsol]->urm=c;
d->viz=1;
nod *g=v[d->info];
while(g->urm)
{
g=g->urm;
if(g->info==k)
{g->viz=0;break;}
}
}
}
else if(d->info!=tata[k])
low[k]=minv(low[k],disc[d->info]);
}
}
void dfs(int k)
{
viz[k]=0;
nod *d=v[k];
st_sol[++siz]=k;
while(d->urm)
{
d=d->urm;
if(viz[d->info] && !d->viz)
dfs(d->info);
}
}
int main()
{
int x,y;
fin>>n>>m;
for(int i=1;i<=n;i++)
{
v[i]=new nod;
v[i]->info=i;
v[i]->urm=0;
v[i]->viz=0;
}
for(int i=1;i<=m;i++)
{
fin>>x>>y;
if(!v[x]->urm)
{
c=new nod;
c->info=y;
c->urm=0;
c->viz=0;
v[x]->urm=c;
e[x]=c;
}
else
{
c=new nod;
c->info=y;
c->urm=0;
c->viz=0;
e[x]->urm=c;
e[x]=c;
}
if(!v[y]->urm)
{
c=new nod;
c->info=x;
c->urm=0;
c->viz=0;
v[y]->urm=c;
e[y]=c;
}
else
{
c=new nod;
c->info=x;
c->urm=0;
c->viz=0;
e[y]->urm=c;
e[y]=c;
}
}
for(int i=1;i<=n;i++)
if(!viz[i])
solve(i);
for(int i=1;i<=n;i++)
if(viz[i])
{
siz=0;
dfs(i);
if(siz>1)
add_sol();
}
fout<<nrsol<<"\n";
for(int i=1;i<=nrsol;i++)
{
c=sol[i];
fout<<c->info<<" ";
while(c->urm)
{
c=c->urm;
fout<<c->info<<" ";
}
fout<<"\n";
}
return 0;
}