Pagini recente » Cod sursa (job #3276047) | Cod sursa (job #2302301) | Cod sursa (job #2673194) | Cod sursa (job #3160062) | Cod sursa (job #2972903)
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
ifstream cin("biconex.in");
ofstream cout("biconex.out");
int n,m,a,b;
vector<vector<int>> sirad;
stack<pair<int,int>>stk;
vector<int> lvl,low;
vector<vector<int>>cbc;
void cache(int a,int b)
{
vector<int> c;
while(true)
{
int tx = stk.top().first,
ty = stk.top().second;
c.push_back(tx);
c.push_back(ty);
stk.pop();
if(tx == a && ty == b)break;
}
cbc.push_back(c);
}
void Bicon(int x,int parent,int idx)
{
lvl[x] = low[x] = idx;
for(auto i : sirad[x])
{
if(i==parent)continue;
if(lvl[i] == -1)
{
stk.push({x,i});
Bicon(i,x,idx+1);
low[x] = min(low[x],low[i]);
if(low[i] >= lvl[x])
cache(x,i);
}
else low[x] = min(low[x],lvl[i]);
}
}
void compute()
{
for(int i=1;i<=n;++i)
if(lvl[i] == -1)
Bicon(i,0,0);
}
int main()
{
cin>>n>>m;
sirad = vector<vector<int>>(n+1);
lvl = low = vector<int>(n+1,-1);
while(m--)
{
cin>>a>>b;
sirad[a].push_back(b);
sirad[b].push_back(a);
}
compute();
cout<<cbc.size()<<'\n';
for(auto& i : cbc)
{
sort(i.begin(),i.end());
i.erase(unique(i.begin(),i.end()),i.end());
for(auto j : i)
cout<<j<<' ';
cout<<'\n';
}
return 0;
}