Pagini recente » Cod sursa (job #2058235) | Cod sursa (job #2078072) | Cod sursa (job #1386843) | Cod sursa (job #2445967) | Cod sursa (job #2144294)
#include <fstream>
#include <vector>
#include <stack>
#define MAX 100100
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
vector<int> a[MAX];
vector<vector<int> > sol;
vector<int>::iterator it;
stack<pair<int,int> > st;
int i,j,n,x,y,m,r,nrb;
int comp[MAX],nro[MAX],low[MAX];
bool viz[MAX];
void add(int x,int y)
{
++nrb;
int a,b;
vector<int> v;
v.push_back(x);
v.push_back(y);
comp[x]=nrb;
comp[y]=nrb;
while(st.top().first!=x || st.top().second!=y)
{
a=st.top().first;
b=st.top().second;
st.pop();
if(comp[a]!=nrb)
{
v.push_back(a);
comp[a]=nrb;
}
if(comp[b]!=nrb)
{
comp[b]=nrb;
v.push_back(b);
}
}
st.pop();
sol.push_back(v);
}
void biconex(int x,int t)
{
int fiu;
low[x]=nro[x];
viz[x]=1;
vector<int>::iterator it;
for(it=a[x].begin() ; it!=a[x].end() ; ++it)
{
fiu=*it;
if(fiu!=t)
{
if(!viz[fiu])
{
nro[fiu]=nro[x]+1;
st.push(make_pair(x,fiu));
biconex(fiu,x);
low[x]=min(low[x],low[fiu]);
if(low[fiu]>=nro[x])
add(x,fiu);
}
else
low[x]=min(low[x],nro[fiu]);
}
}
}
int main()
{
f>>n>>m;
for(i=1 ; i<=m ; ++i)
{
f>>x>>y;
a[x].push_back(y);
a[y].push_back(x);
}
for(i=1 ; i<=n ; ++i)
if(!comp[i])
{
nro[i]=0;
biconex(i,0);
}
g<<nrb<<'\n';
for(i=0 ; i<sol.size() ; ++i)
{
for(j=0 ; j<sol[i].size() ; ++j)
g<<sol[i][j]<<" ";
g<<'\n';
}
return 0;
}