Pagini recente » Cod sursa (job #1712603) | Cod sursa (job #1889260) | Cod sursa (job #843739) | Cod sursa (job #1075706) | Cod sursa (job #600548)
Cod sursa(job #600548)
#include <fstream>
#include <cstring>
#define X1 100001
using namespace std;
ifstream in;
ofstream out;
struct graf
{
int nod;
graf *link;
}*v[X1];
struct sol
{
int nod;
sol *link;
}*biconex[X1];
struct stack
{
int x,y;
}st[X1];
int T[X1],level[X1],low[X1];
char use[X1];
int size=0,cnt=0;
inline void add(int x,int y)
{
graf *p;
p=new graf;
p->nod=y;
p->link=v[x];
v[x]=p;
}
inline void addsol(int x,int y)
{
sol *p;
p=new sol;
p->nod=y;
p->link=biconex[x];
biconex[x]=p;
}
inline void df(int nod)
{
graf *p;
int x,y;
use[nod]=1;
p=v[nod];
for(;p!=NULL;p=p->link)
{
if(T[nod]!=p->nod&&level[nod]>=level[p->nod])
{
st[++size].x=nod;
st[size].y=p->nod;
}
if(use[p->nod]==0)
{
T[p->nod]=nod;
level[p->nod]=level[nod]+1;
low[p->nod]=level[p->nod];
df(p->nod);
if(low[p->nod]<low[nod]) low[nod]=low[p->nod];
if(low[p->nod]>=level[nod])
{
++cnt;
do
{
x=st[size].x;
y=st[size].y;
if(T[y]==x) addsol(cnt,y);
--size;
}
while(x!=nod||y!=p->nod);
addsol(cnt,nod);
}
}
else
if(T[nod]!=p->nod&&low[nod]>level[p->nod])
low[nod]=level[p->nod];
}
}
int main()
{
int M,N,x,y;
in.open("biconex.in");
in>>N>>M;
for(;M;--M)
{
in>>x>>y;
add(x,y);
add(y,x);
}
in.close();
memset(use,0,sizeof(use));
level[1]=0;
low[1]=0;
df(1);
out.open("biconex.out");
out<<cnt<<'\n';
for(int i=1;i<=cnt;++i)
{
for(sol *p=biconex[i];p!=NULL;p=p->link)
out<<p->nod<<' ';
out<<'\n';
}
out.close();
return 0;
}