Pagini recente » Cod sursa (job #1292623) | Cod sursa (job #2517834) | Cod sursa (job #2460010) | Cod sursa (job #1970936) | Cod sursa (job #1140097)
#include<fstream>
#include<algorithm>
#include<vector>
#include<stack>
#define pb push_back
using namespace std;
vector <int> gr[100001];
vector <int> cbc[200001];
stack <pair <int, int> > com;
int ncbc;
bool viz[100001];
int niv[100001];
void dfs(int vf, int tata, int nivel)
{
int i,nivi=nivel;
int lim=gr[vf].size();
viz[vf]=1;
niv[vf]=nivel;
for(i=0;i<lim;i++)
{
if(!viz[gr[vf][i]])
{
com.push(make_pair(vf,gr[vf][i]));
dfs(gr[vf][i],vf,nivel+1);
if(niv[gr[vf][i]]>=nivel)
{
ncbc++;
while((com.top().first!=vf)||(com.top().second!=gr[vf][i]))
{
cbc[ncbc].pb(com.top().second);
com.pop();
}
cbc[ncbc].pb(com.top().second);
cbc[ncbc].pb(com.top().first);
com.pop();
}
}
if(gr[vf][i]!=tata)
nivi=min(nivi,niv[gr[vf][i]]);
}
niv[vf]=nivi;
}
int main()
{
int n,m;
int x,y;
int i,j;
int lim;
ifstream f("biconex.in");
f>>n>>m;
for(i=1;i<=m;i++)
{
f>>x>>y;
gr[x].pb(y);
gr[y].pb(x);
}
f.close();
for(i=1;i<=n;i++)
if(!viz[i])
dfs(i,0,1);
ofstream g("biconex.out");
g<<ncbc<<'\n';
for(i=1;i<=ncbc;i++)
{
lim=cbc[i].size();
for(j=0;j<lim;j++)
g<<cbc[i][j]<<' ';
g<<'\n';
}
g.close();
return 0;
}