Pagini recente » Cod sursa (job #2312045) | Cod sursa (job #455030) | Cod sursa (job #115837) | Cod sursa (job #1102442) | Cod sursa (job #1870577)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
struct nod
{
int val;
nod *urm;
};
typedef nod *pnod;
pnod p,v[100003];
struct segm
{
int x,y;
};
segm muchie[400003];
void ad(int x,int y)
{
p=new nod;
p->val=y;
p->urm=v[x]->urm;
v[x]->urm=p;
}
int ind[100003],mind[100003],comp[400003],cate,inc,ct,index,ss;
int t[100003];
void dfs(int i)
{
index+=1;
ss+=1;
ind[i]=index;
mind[i]=index;
muchie[ss].x=i;
pnod p;
p=v[i]->urm;
while(p)
{
if(ind[p->val]!=0)
{
if(t[i]!=p->val and mind[i]>ind[p->val])
mind[i]=ind[p->val];
}
else
{
muchie[ss].y=p->val;
t[p->val]=i;
dfs(p->val);
if(mind[i]>mind[p->val])
mind[i]=mind[p->val];
if(ind[i]<=mind[p->val])
{
cate+=1;
ct+=1;
inc=ct;
while(muchie[ss].x!=i and muchie[ss].y!=p->val)
{
comp[ct]=muchie[ss].x;
ct+=1;
ss-=1;
}
comp[ct]=i;
ct+=1;
/*comp[ct]=p->val;
ct+=1;*/
sort(comp+inc,comp+ct);
}
}
p=p->urm;
}
}
int main()
{
int i,j,x,y,n,m;
f>>n>>m;
for(i=1;i<=n;i++)
{
v[i]=new nod;
v[i]->urm=0;
}
for(i=1;i<=m;i++)
{
f>>x>>y;
ad(x,y);
ad(y,x);
}
for(i=1;i<=n;i++)
{
if(ind[i]==0)
{
index=0;
ss=0;
dfs(i);
}
}
g<<cate<<'\n';
j=1;
for(i=1;i<=cate;i++)
{
while(comp[j]!=0)
{
g<<comp[j]<<" ";
j+=1;
}
j+=1;
g<<'\n';
}
return 0;
}