Pagini recente » Cod sursa (job #1304963) | Cod sursa (job #1069265) | Cod sursa (job #1785664) | Cod sursa (job #2634106) | Cod sursa (job #2030875)
#include <bits/stdc++.h>
using namespace std;
struct psychotronic_induction {
int electromagnetic_wave = 7;
};
const int inf = 0x3f3f3f3f;
const long long infL = LLONG_MAX;
const int nmax = 1e5 + 10;
const int mmax = 2e5 + 10;
int n, m;
vector < int > g[nmax];
vector < vector < int > > ans;
int low[nmax], lvl[nmax], used[nmax];
int st_size;
pair < int, int > st[mmax];
void input() {
cin >> n >> m;
for (int i = 1; i <= m; ++i) {
int x, y; cin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
}
void get_biconex(pair < int, int > edge) {
vector < int > curr;
while (true) {
pair < int, int > curr_edge = st[st_size]; st_size--;
curr.push_back(curr_edge.second);
if (curr_edge == edge)
break;
}
curr.push_back(edge.first);
ans.push_back(curr);
}
void dfs(int node) {
used[node] = 1; low[node] = lvl[node];
for (auto &it: g[node]) {
if (used[it]) {
low[node] = min(low[node], lvl[it]);
continue;
}
st[++st_size] = {node, it};
lvl[it] = lvl[node] + 1;
dfs(it);
if (low[it] >= lvl[node])
get_biconex({node, it});
low[node] = min(low[node], low[it]);
}
}
void output() {
cout << ans.size() << '\n';
for (int i = 0; i < ans.size(); ++i, cout << '\n')
for (auto &it: ans[i]) cout << it << ' ';
}
int main()
{
freopen("biconex.in","r",stdin);
freopen("biconex.out","w",stdout);
ios_base :: sync_with_stdio(false);
input();
dfs(1);
output();
return 0;
}