Pagini recente » Cod sursa (job #2254833) | Cod sursa (job #60085) | Cod sursa (job #1358698) | Cod sursa (job #1714867) | Cod sursa (job #1335408)
#include<fstream>
//#include<iostream>
#include<vector>
#define st s.top()
#include<stack>
#define pb push_back
using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");
int N,M,t[100005],niv[100005],l[100005],mm,u,af[100005];
bool viz[100005];
vector<int> v[100005];
stack< pair<int,int> > s;
vector< pair<int,int> > sol[200005];
vector< pair<int,int> > :: iterator it;
void df(int i);
int main()
{
in>>N>>M;
int i,a,b;
while(M--)
{
in>>a>>b;
v[a].pb(b);
v[b].pb(a);
}
df(1);
out<<u<<'\n';
for(i=1;i<=u;++i)
{
for(it=sol[i].begin();it!=sol[i].end();++it)
{
if(af[it->first]!=i)
out<<it->first<<' ',af[it->first]=i;
if(af[it->second]!=i)
out<<it->second<<' ',af[it->second]=i;
}
out<<'\n';
}
}
void df(int i)
{
viz[i]=1;
niv[i]=niv[t[i]]+1;
l[i]=niv[i];
vector<int> :: iterator it;
for(it=v[i].begin();it!=v[i].end();++it)
{
if(*it!=t[i] && niv[*it]<niv[i])
{
s.push( make_pair(i,*it));
++mm;
}
if(!viz[*it])
{
t[*it]=i;
df(*it);
if(l[i]>l[*it]) l[i]=l[*it];
if(l[*it]>=niv[i])
{
//cout<<i<<' '<<*it<<'\n';
++u;
while(st.first!=i && st.second!=*it)
{
//cout<<'('<<st.first<<';'<<st.second<<')'<<' ';
sol[u].push_back(st);
s.pop();
}
//cout<<'('<<st.first<<';'<<st.second<<')'<<' ';
sol[u].push_back(st);
s.pop();
//cout<<'\n';
}
}
else
if(*it!=t[i] && l[i]>niv[*it]) l[i]=niv[*it];
}
}