# Cod sursa(job #2811696)

Utilizator Data 2 decembrie 2021 21:50:25 Componente biconexe 100 cpp-64 done Arhiva educationala 1.61 kb
``````#include<fstream>
#include<vector>
#include<stack>
#include<algorithm>
using namespace std;
ifstream cin("biconex.in");
ofstream cout("biconex.out");
vector<vector<int> >mu,ra;
vector<int>c;
stack<pair<int,int>>st;
int n,m,low[100002],f[100002],cnt;
void remake(int x,int y)
{
//cout<<'\n';
cnt++;
ra.push_back(c);
int tx,ty;
do
{
ty=st.top().second;
tx=st.top().first;
ra[cnt].push_back(ty);
ra[cnt].push_back(tx);
// cout<<tx<<' '<<ty<<'\n';
st.pop();
}
while(ty!=y || tx!=x);
//cout<<tx<<' '<<ty<<'\n';
//st.pop();
}
void DF(int x,int nr,int nod)
{
//cout<<x<<'\n';
low[x]=f[x]=nr;
for(int i=0; i<mu[x].size(); i++)
{
if(f[mu[x][i]]==0)
{
st.push(make_pair(x,mu[x][i]));
DF(mu[x][i],nr+1,x);
low[x]=min(low[x],low[mu[x][i]]);
if(low[mu[x][i]]>=f[x])
remake(x,mu[x][i]);
}
else
low[x]=min(low[x],f[mu[x][i]]);
}
//cout<<x<<'\n';
}
int main()
{
cin>>n>>m;
ra.push_back(c);
mu.resize(n+1);
for(int i=1; i<=m; i++)
{
int x,y;
cin>>x>>y;
mu[x].push_back(y);
mu[y].push_back(x);
}
DF(1,1,0);
cout<<cnt<<'\n';
for(int i=1; i<=cnt; i++)
{
int x=-1;
sort(ra[i].begin(),ra[i].end());
for(int j=0; j<ra[i].size(); j++)
if(ra[i][j]!=x)
{
x=ra[i][j];
cout<<ra[i][j]<<' ';
}
cout<<'\n';
}
}
``````