Pagini recente » Cod sursa (job #3212968) | Cod sursa (job #2581049) | Cod sursa (job #3255884) | Cod sursa (job #2406099) | Cod sursa (job #3225747)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
const int Nmax=1e5+5;
vector<int> v[Nmax];
int dfn[Nmax],low[Nmax];
vector<vector<int>> ans;
bitset<Nmax> viz;
stack<pair<int,int>> st;
///DFN = timpul la care am intrat intr-un nod prima oara
///LOW = timpul minim(DFN-ul minim) la care ajung in arborele dfs din nod
///punct de articulatie , daca dfn[nod]<=low[copil]
///deoarece oricum merg,ajung din copil intr-un nod cu
///timp mai mare ca nod, formand astfel o componenta biconexa
void createans(int x,int y)
{
vector<int> comp;
int tx=-1,ty=-1;
while(tx!=x || ty!=y)
{
tx=st.top().first;
ty=st.top().second;
st.pop();
comp.push_back(ty);
if(tx==x && ty==y) comp.push_back(tx);
}
ans.push_back(comp);
}
void dfs(int nod,int prev,int timp)
{
viz[nod]=1;
dfn[nod]=timp;
low[nod]=timp;
for(int u:v[nod])
{
///if(nod==1) cout<<u<<' ';
if(u==prev) continue;
if(!viz[u])
{
st.push({nod,u});
dfs(u,nod,timp+1);
low[nod]=min(low[nod],low[u]);
///cout<<nod<<' '<<u<<' '<<dfn[nod]<<' '<<low[u]<<'\n';
if(dfn[nod]<=low[u])
{
createans(nod,u);
}
}
else
{
low[nod]=min(low[nod],dfn[u]);
}
}
return;
}
int main()
{
int n,m;
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);
}
dfs(1,0,0);
fout<<ans.size()<<'\n';
for(auto v:ans)
{
for(auto x:v)
{
fout<<x<<' ';
}
fout<<'\n';
}
return 0;
}