Pagini recente » Cod sursa (job #1895821) | Cod sursa (job #2965146) | Cod sursa (job #1964852) | Cod sursa (job #1760910) | Cod sursa (job #2369290)
#include <iostream>
#include <vector>
#include <fstream>
#include <stack>
#define nmax 100003
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
int n,m, niv[nmax], low[nmax], viz[nmax], nr;
vector <int> v[nmax], cbc[nmax];
stack<int> s;
void citire()
{
int i,x,y;
f>>n>>m;
for(i=1; i<=m; i++)
{
f>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
}
void dfs(int nod, int tata)
{
int i,next,vf;
s.push(nod);
niv[nod]=niv[tata]+1;
low[nod]=niv[nod];
viz[nod]=1;
for(i=0; i<v[nod].size(); i++)
{
next=v[nod][i];
if(next!=tata)
{
if(viz[next])
{
if(low[nod]>niv[next])
low[nod]=niv[next];
}
else
{
dfs(next,nod);
if(low[nod]>low[next])
low[nod]=low[next];
if(niv[nod]<=low[next])
{
vf=s.top();
while(vf!=next)
{
cbc[nr].push_back(vf);
s.pop();
vf=s.top();
}
cbc[nr].push_back(next);
s.pop();
cbc[nr].push_back(nod);
nr++;
}
}
}
}
}
int main()
{
citire();
dfs(1,0);
int i,j;
g<<nr<<"\n";
for(i=0; i<nr; i++)
{for(j=0; j<cbc[i].size(); j++)
g<<cbc[i][j]<<" ";
g<<"\n";}
f.close();
g.close();
return 0;
}