Pagini recente » Prezentare infoarena | Cod sursa (job #2781424) | Cod sursa (job #2708843) | Cod sursa (job #48974) | Cod sursa (job #3251874)
#include <bits/stdc++.h>
using namespace std;
#define INFILE "biconex.in"
#define OUTFILE "biconex.out"
const int N_MAX = 100000;
int n, m;
int d[N_MAX + 5];
int level[N_MAX + 5];
bool visited[N_MAX + 5];
vector<int> adj[N_MAX + 5];
stack<int> s;
vector<vector<int> > ans;
void addBiconexComponent(int node, int son){
vector<int> aux;
while(!s.empty() && s.top() != son){
aux.push_back(s.top());
s.pop();
}
s.pop();
aux.push_back(son);
aux.push_back(node);
ans.push_back(aux);
}
void dfs(int node, int parent){
visited[node] = true;
for(auto &to : adj[node]){
if(to == parent) continue;
if(visited[to]) d[node] = min(d[node], level[to]);
else {
s.push(to);
level[to] = level[node] + 1;
dfs(to, node);
d[node] = min(d[node], d[to]);
if(d[to] >= level[node]){
addBiconexComponent(node, to);
}
}
}
}
void solve(){
cin >> n >> m;
for(int i = 0; i < m; ++i){
int node1, node2; cin >> node1 >> node2;
adj[node1].push_back(node2);
adj[node2].push_back(node1);
}
for(int i = 1; i <= n; ++i){
if(!visited[i]) dfs(i, 0);
}
cout << ans.size() << '\n';
for(int i = 0; i < ans.size(); ++i){
for(auto &node : ans[i]){
cout << node << " ";
}
cout << '\n';
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
freopen(INFILE, "r", stdin);
freopen(OUTFILE, "w", stdout);
solve();
return 0;
}