Pagini recente » Cod sursa (job #1190441) | Cod sursa (job #2044236) | Cod sursa (job #2109237) | Cod sursa (job #892268) | Cod sursa (job #2982114)
#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 t){
stk.push_back(t);
stk.push_back(k);
int nrfi = 0;
vis[k] = 1;
h[k] = h[t] + 1;
low[k] = h[k];
for(int to : ad[k]){
if(vis[to] == 0){
nrfi++;
dfs(to,k);
low[k] = min(low[k],low[to]);
if(low[to]>=h[k]){
nc[k] = 1;
while(stk.back()!=k){
if(cxx.back().size())
if(cxx.back().back()==stk.back())
goto nd;
cxx.back().push_back(stk.back());
nd:
stk.pop_back();
}
cxx.back().push_back(k);
stk.pop_back();
cxx.push_back({});
}
}
else // just using 1 back edge
low[k] = min(low[k],h[to]);
}
if(t == 0 && nrfi == 1){
nc[k] = 0;
}
}
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";
}
}