Pagini recente » Cod sursa (job #1203659) | Cod sursa (job #287796) | Cod sursa (job #702220) | Cod sursa (job #197359) | Cod sursa (job #3148218)
#include <fstream>
#include <vector>
#define max_sz 100003
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int n,m;
vector <int> v[max_sz];
vector <int> st;
bool viz[max_sz];
int lv[max_sz];
int mlv[max_sz];
int comp_nr;
vector <int> sol[max_sz];
void dfs(int nod,int p)
{
viz[nod]=true;
lv[nod]=lv[p]+1;
mlv[nod]=lv[nod];
st.push_back(nod);
for(auto& i : v[nod])
if(i!=p)
{
if(viz[i])
mlv[nod]=min(mlv[nod],lv[i]);
else
{
dfs(i,nod);
mlv[nod]=min(mlv[nod],mlv[i]);
if(mlv[i]>=lv[nod])
{
comp_nr++;
while(st.back()!=i)
{
sol[comp_nr].push_back(st.back());
st.pop_back();
}
sol[comp_nr].push_back(i);
st.pop_back();
sol[comp_nr].push_back(nod);
}
}
}
}
int main()
{
fin>>n>>m;
for(int i =1; i<=m; i++)
{
int x,y;
fin>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
for(int i=1;i<=n;i++)
{
if(!viz[i])
dfs(i,0);
}
fout<<comp_nr<<'\n';
for(int i=1; i<=comp_nr; i++)
{
for(auto& j : sol[i])
fout<<j<<' ';
fout<<'\n';
}
}