Pagini recente » Cod sursa (job #1787523) | Rating Dumitru Nicoleta (nicoletaluciana) | Cod sursa (job #3232112) | Cod sursa (job #1487762) | Cod sursa (job #2982160)
#include <bits/stdc++.h>
using namespace std;
const int nmx = 1e5 + 4;
vector<int> ad[nmx];
int low[nmx],h[nmx],vis[nmx];
int nc[nmx];
vector<vector<int>> cxx={{}};
#if 1
#define cin fin
#define cout fout
ifstream fin("biconex.in");
ofstream fout("biconex.out");
#endif // 1
vector<int> stk;
void dfs(int k,int tata){
stk.push_back(k);
vis[k] = 1;
h[k] = h[tata] + 1;
low[k] = h[k];
int nrfi = 0;
for(int to : ad[k]){
if(to==tata)
continue;
if(vis[to] == 0){
nrfi++;
dfs(to,k);
low[k] = min(low[k],low[to]);
if(h[k]<=low[to]){
nc[k] = 1;
while(stk.back()!=to){
cxx.back().push_back(stk.back());
stk.pop_back();
}
cxx.back().push_back(stk.back());
stk.pop_back();
cxx.back().push_back(k);
cxx.push_back({});
}
}
else{
low[k] = min(low[k],h[to]);
}
}
if(tata == 0 && nrfi==1)
nc[k] = 0;
if(tata == 0 && nrfi == 0){
cxx.back().push_back(k);
cxx.push_back({});
}
}
int main(){
int n,m;
cin >> n >> m;
while(m--){
int u,v;
cin >> u >> v;
ad[u].push_back(v);
ad[v].push_back(u);
}
for(int i=1;i<=n;i++)
if(vis[i]==0)
dfs(i,0);
cout << cxx.size()-1 << "\n";
for(auto& cx : cxx){
for(int el : cx)
cout << el << " ";
cout << "\n";
}
}