Pagini recente » Cod sursa (job #2789668) | Cod sursa (job #73904) | Cod sursa (job #445001) | Cod sursa (job #1742782) | Cod sursa (job #1163187)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
#define MAX 100100
#define pb push_back
#define mp make_pair
typedef vector <int> :: iterator iter;
vector <int> G[MAX];
vector< vector < int > > ans;
int ad[MAX], ad_fiu[MAX], dr, viz[MAX];
pair <int, int> st[MAX];
void make_component(int x, int y)
{
int nx, ny;
vector <int> xy;
do{
nx=st[dr].first;
ny=st[dr].second;
dr--;
xy.pb(ny);
}while(nx!=x || ny!=y);
xy.pb(nx);
ans.pb(xy);
}
void df(int nod, int parinte, int adancime)
{
viz[nod]=1;
ad[nod]=adancime;
ad_fiu[nod]=adancime;
for(iter it=G[nod].begin();it!=G[nod].end();it++)
{
if(*it==parinte)
continue;
if(viz[*it])
{
ad_fiu[nod]=min(ad_fiu[nod], ad[*it]);
}
else
{
st[++dr]=mp(nod, *it);
df(*it, nod, adancime+1);
ad_fiu[nod]=min(ad_fiu[nod], ad_fiu[*it]);
if(ad_fiu[*it]>=ad[nod])
make_component(nod, *it);
}
}
}
int main()
{
int n, m, x, y;
fin>>n>>m;
while(m--)
{
fin>>x>>y;
G[x].pb(y);
G[y].pb(x);
}
df(1, 0, 1);
fout<<ans.size()<<"\n";
while(ans.size())
{
for(iter it=ans[ans.size()-1].begin();it!=ans[ans.size()-1].end();it++)
{
fout<<*it<<" ";
}
fout<<"\n";
ans.pop_back();
}
}