Pagini recente » Cod sursa (job #2463147) | Cod sursa (job #2610503)
#include <iostream>
#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];
int 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;
}