Pagini recente » Cod sursa (job #2354068) | Cod sursa (job #3214780) | Cod sursa (job #1435714) | Cod sursa (job #3030567) | Cod sursa (job #1314367)
#include <fstream>
#include <list>
#include <stack>
#define DIM 100001
#include <queue>
using namespace std;
ifstream in ("biconex.in");
ofstream out ("biconex.out");
int biconex, bicon[DIM], dad[DIM], idx[DIM], lowl[DIM];
int index, n, m, a, b;
stack < pair<int, int> > stk;
queue <int> q;
list <int> nod[DIM];
void build(int x, int y)
{
int v1, v2, ok=0;
biconex++;
do
{
v1=stk.top().first;
v2=stk.top().second;
if((v1==x&&v2==y)||(v1==y&&v2==x))
{
ok=1;
}
if(bicon[v1]!=biconex)
{
q.push(v1);
bicon[v1]=biconex;
}
if(bicon[v2]!=biconex)
{
q.push(v2);
bicon[v2]=biconex;
}
stk.pop();
}while(ok==0);
//stk.push(make_pair(x, y));
q.push(0);
}
void tarjan(int vf)
{
idx[vf]=(++index);
lowl[vf]=index;
for( list <int>::iterator j=nod[vf].begin(); j!=nod[vf].end(); ++j)
{
if(idx[*j]==0)
{
dad[*j]=vf;
stk.push(make_pair(vf, *j));
tarjan(*j);
lowl[vf]=min(lowl[vf], lowl[*j]);
if(lowl[*j]>=idx[vf])
build(*j, vf);
}
else
{
if(dad[vf]!=(*j))
{
//if(idx[*j]<lowl[vf])
//stk.push(make_pair(vf, (*j)));
lowl[vf]=min(lowl[vf], idx[*j]);
}
}
}
}
int main()
{
in>>n>>m;
while(m--)
{
in>>a>>b;
nod[a].push_back(b);
nod[b].push_back(a);
}
for(int i=1; i<=n; ++i)
{
if(idx[i]==0)
{
index=0;
tarjan(i);
}
}
out<<biconex<<"\n";
while(!q.empty())
{
a=q.front();
if(a!=0)
out<<a<<" ";
else out<<"\n";
q.pop();
}
in.close();
out.close();
return 0;
}