Pagini recente » Cod sursa (job #209403) | Cod sursa (job #2527643) | Cod sursa (job #2128282) | Cod sursa (job #1524726) | Cod sursa (job #600534)
Cod sursa(job #600534)
#include <fstream>
#include <cstring>
#include <vector>
#define X1 100001
using namespace std;
struct stack
{
int x,y;
}st[X1];
ifstream in;
ofstream out;
vector <int> v[X1];
vector <int> biconex[X1];
int use[X1],T[X1],low[X1],level[X1],er[X1];
int cnt=0;
inline void df(int nod)
{
int x,y;
use[nod]=1;
for(vector <int>::iterator it=v[nod].begin();it!=v[nod].end();++it)
{
if(T[nod]!=*it&&level[nod]>=level[*it])
{
st[++st[0].x].x=nod;
st[st[0].x].y=*it;
}
if(!use[*it])
{
T[*it]=nod;
level[*it]=level[nod]+1;
low[*it]=level[*it];
df(*it);
if(low[nod]>low[*it]) low[nod]=low[*it];
if(low[*it]>=level[nod])
{
++cnt;
x=*it;
do
{
biconex[cnt].push_back(x);
x=T[x];
}
while(x!=nod);
biconex[cnt].push_back(nod);
/*memset(er,0,sizeof(er));
if(st[0].x)
do
{
x=st[st[0].x].x;
y=st[st[0].x].y;
if(!er[x])
{
biconex[cnt].push_back(x);
er[x]=1;
}
if(!er[y])
{
biconex[cnt].push_back(y);
er[y]=1;
}
st[st[0].x].x=0;
st[st[0].x].y=0;
--st[0].x;
}
while((x!=*it||y!=nod)&&(x!=nod||y!=*it)&&st[0].x);*/
}
}
else
if(T[nod]!=*it)
if(low[nod]>level[*it])
low[nod]=level[*it];
}
}
int main()
{
int M,N,x,y;
in.open("biconex.in");
in>>N>>M;
for(;M;--M)
{
in>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
in.close();
memset(use,0,sizeof(use));
memset(level,0,sizeof(level));
memset(low,0,sizeof(low));
memset(T,0,sizeof(T));
for(int i=1;i<=N;++i)
if(!use[i]) df(i);
out.open("biconex.out");
out<<cnt<<'\n';
for(int nod=1;nod<=cnt;++nod)
{
for(vector <int>::iterator it=biconex[nod].begin();it!=biconex[nod].end();++it)
out<<*it<<' ';
out<<'\n';
}
out.close();
return 0;
}