Pagini recente » Cod sursa (job #897541) | Cod sursa (job #3193483) | Cod sursa (job #2321784) | Cod sursa (job #1517435) | Cod sursa (job #3283815)
#pragma GCC optimize ("Ofast")
#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 tin[Nmax],low[Nmax];
vector<vector<int>> ans;
bitset<Nmax> viz;
int timer=1;
stack<int> st;
void dfs(int nod,int prv)
{
st.push(nod);
viz[nod]=1;
tin[nod]=timer++;
low[nod]=tin[nod];
for(int u:v[nod])
{
if(u==prv) continue;
if(!viz[u])
{
dfs(u,nod);
low[nod]=min(low[nod],low[u]);
}
else low[nod]=min(low[nod],tin[u]);
}
if(prv!=0 && low[nod]>=tin[prv])
{
///nod->prv e crit edge
vector<int> c;
while(true)
{
/// adaug nodurile din "subarborele" lui nod
int x=st.top();
st.pop();
c.push_back(x);
if(x==nod) break;
}
/// subarb lui nod + prv formeaza o componenta biconexa maxima
c.push_back(prv);
ans.push_back(c);
}
}
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);
fout<<ans.size()<<'\n';
for(auto vi:ans)
{
for(auto x:vi) fout<<x<<' ';
fout<<'\n';
}
return 0;
}