Pagini recente » Monitorul de evaluare | Cod sursa (job #1522214) | Cod sursa (job #391500) | Cod sursa (job #3236767) | Cod sursa (job #1863675)
#include <fstream>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
int p,n,m,ok;
int nivel[100005],l[100005],tata[100005],a[100005];
struct muchie
{
int i,j;
}st[300005];
int u =0;
struct nod
{
int info;
nod*urm;
}*pt[100005];
struct comp
{
nod *q;
comp *next;
}*elemx;
int k;
void inserarenod(nod *&point,int val)
{
nod *cap=new nod;
cap->info=val;
cap->urm=point;
point=cap;
}
void inserarecomp(comp *&point)
{
comp *cap=new comp;
cap->q=NULL;
cap->next=point;
point= cap;
}
void Afisarenod(nod *&point)
{
nod *cap=point;
while(cap!=NULL)
{
g<<cap->info<<" ";
cap=cap->urm;
}
}
void Afisarecomp(comp *& point)
{
comp *cap=point;
while(cap!=NULL)
{
Afisarenod(cap->q);
g<<'\n';
cap=cap->next;
}
}
void drum(int xp)
{
while(l[tata[xp]]>l[xp])
{
l[tata[xp]]= l[xp];
xp=tata[xp];
}
}
void compbiconex(int x, int y)
{
int ct=0, verif=0;
k++;
inserarecomp(elemx);
while(verif==0)
{
if(a[st[u].i]!=k)
{
ct++;
a[st[u].i]=k;
inserarenod(elemx->q,st[u].i);
}
if(a[st[u].j]!=k)
{
ct++;
a[st[u].j]=k;
inserarenod(elemx->q,st[u].j);
}
if(st[u].i== x && st[u].j==y)
verif =1;
st[u].i=st[u].j=0;
u--;
}
}
void df2(int xp, int r)
{
nod *cap=pt[xp];
int y;
while(cap!=NULL)
{
y=cap->info;
if(y!=tata[xp])
{
if(nivel[y]!=0 && nivel[y]<nivel[xp])
{
if(l[xp]>nivel[y])
{
l[xp]=nivel[y];
drum(xp);
}
u++;
st[u].i=xp;
st[u].j=y;
}
else
if(nivel[y]==0)
{
nivel[y]=nivel[xp]+1;
l[y]=nivel[y];
tata[y]=xp;
u++;
st[u].i=xp;
st[u].j=y;
df2(y,r);
if(l[y]>=nivel[xp])
compbiconex(xp,y);
}
}
cap=cap->urm;
}
}
int main()
{
int a,b,r;
f>>n>>m;
for(int i=1;i<=n;i++)
pt[i]=NULL;
elemx=NULL;
for(int i=1;i<=m;i++)
{
f>>a>>b;
inserarenod(pt[a],b);
inserarenod(pt[b],a);
}
r=1;
tata[r]=0;
nivel[r]=1;
l[r]=1;
df2(r,r);
g<<k<<'\n';
Afisarecomp(elemx);
return 0;
}