Pagini recente » Cod sursa (job #543600) | Cod sursa (job #1341874) | Profil TakeshiTikano | Cod sursa (job #1018844) | Cod sursa (job #1503487)
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
ifstream cin("biconex.in");
ofstream cout("biconex.out");
const int LIM=100001, ARB=1, INT=2;
int n, m, low[LIM], nr_sol;
struct muc
{
int a, b, cod;
}v[LIM+LIM];
vector <int> gr[LIM], sol[LIM];
stack <int> s;
char viz[LIM];
void dfs(int nod, int niv)
{
low[nod]=niv;
for(int i=0; i<gr[nod].size(); ++i)
{
int fiu=v[ gr[nod][i] ].a;
if(fiu==nod) fiu=v[ gr[nod][i] ].b;
if(!v[ gr[nod][i] ].cod)
if(!low[fiu])
v[ gr[nod][i] ].cod=ARB;
else
v[ gr[nod][i] ].cod=INT;
if(v[ gr[nod][i] ].cod==ARB and low[fiu]) continue;
if(v[ gr[nod][i] ].cod==ARB and !low[fiu])
{
s.push(gr[nod][i]);
dfs(fiu, niv+1);
}
if(v[ gr[nod][i] ].cod==INT)
low[nod]=min(low[nod], low[fiu]);
if(v[ gr[nod][i] ].cod==ARB and low[fiu]>=low[nod])
{
nr_sol++;
bool gata=0;
while(!s.empty() and !gata)
{
if(s.top()==gr[nod][i]) gata=1;
sol[nr_sol].push_back(v[s.top()].a);
sol[nr_sol].push_back(v[s.top()].b);
s.pop();
}
}
low[nod]=min(low[nod], low[fiu]);
}
}
int main()
{
cin>>n>>m;
for(int i=1; i<=m; ++i)
{
cin>>v[i].a>>v[i].b;
gr[v[i].a].push_back(i);
gr[v[i].b].push_back(i);
}
dfs(1, 1);
cout<<nr_sol<<'\n';
for(int i=1; i<=nr_sol; ++i)
{
for(int j=0; j<sol[i].size(); ++j)
if(!viz[ sol[i][j] ])
{
cout<<sol[i][j]<<' ';
viz[ sol[i][j] ]=1;
}
for(int j=0; j<sol[i].size(); ++j)
viz[ sol[i][j] ]=0;
cout<<'\n';
}
return 0;
}