Pagini recente » Profil PopMariusIonut | Profil DARIUSQSS | sitemap.xml | Cod sursa (job #1638813) | Cod sursa (job #3348315)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int n,m,cnt;
vector<int> tim,ti;
vector<bool> viz,art;
vector<vector<int>>a,sol;
stack<int>s;
void dfs(int nod,int rad){
ti[nod]=ti[rad]+1;
tim[nod]=ti[nod];
viz[nod]=1;
s.push(nod);
int fii=0;
for(auto f:a[nod]){
if(f==rad) continue;
if(viz[f]) tim[nod]=min(tim[nod],ti[f]);
else{
dfs(f,nod);
fii++;
tim[nod]=min(tim[nod],tim[f]);
if(rad &&ti[nod]<=tim[f])art[nod]=true;
if(ti[nod]<=tim[f]){
cnt++;
while(s.top()!=f){
sol[cnt].push_back(s.top());
s.pop();
}
sol[cnt].push_back(f);
s.pop();
sol[cnt].push_back(nod);
}
if(!rad&&fii>=2) art[nod]=true;
}
}
}
int main(){
fin>>n>>m;
a.resize(n+1);
sol.resize(n+1);
viz.resize(n+1);
tim.resize(n+1);
ti.resize(n+1);
art.resize(n+1);
int x,y;
for(int i=1;i<=m;i++){
fin>>x>>y;
a[x].push_back(y);
a[y].push_back(x);
}
dfs(1,0);
fout<<cnt;
for(auto x:sol){
sort(x.begin(),x.end());
for(auto y:x) fout<<y<<" ";
fout<<'\n';
}
return 0;
}