Pagini recente » Cod sursa (job #879200) | Cod sursa (job #1867618) | Cod sursa (job #1810897) | Cod sursa (job #1674385) | Cod sursa (job #1899066)
#include <iostream>
#include<fstream>
#include<stack>
#include<queue>
#include<vector>
#define f first
#define s second
#define mp make_pair
#define pb push_back
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
vector<int>v[100010];
vector<int>ans[100010];
stack<pair<int,int> >st;
int timp,n,m,nr,comp[100010],a,b,lev[100010],low[100010],x,y,i,j,it,beg=1,tt[100010];
void add(int x,int y)
{
nr++;
comp[x]=comp[y]=nr;
ans[nr].pb(x);
ans[nr].pb(y);
while(st.top().f!=x || st.top().s!=y)
{
a=st.top().f;
b=st.top().s;
st.pop();
if(comp[a]!=nr)
{
ans[nr].pb(a);
comp[a]=nr;
}
if(comp[b]!=nr)
{
ans[nr].pb(b);
comp[b]=nr;
}
}
st.pop();
}
void df(int x)
{
lev[x]=low[x]=++timp;
for(int k=0; k<v[x].size(); k++)
if(v[x][k]!=tt[x])
{
if(!lev[v[x][k]])
{
st.push(mp(x,v[x][k]));
tt[v[x][k]]=x;
df(v[x][k]);
low[x]=min(low[x],low[v[x][k]]);
if(lev[x]<=low[v[x][k]])
add(x,v[x][k]);
}
else
low[x]=min(low[x],lev[v[x][k]]);
}
}
int main()
{
f>>n>>m;
for(i=1; i<=m; i++)
{
f>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
df(1);
g<<nr<<'\n';
for(i=1; i<=nr; i++)
{
for(j=0; j<ans[i].size(); j++)
g<<ans[i][j]<<' ';
g<<'\n';
}
}