Pagini recente » Cod sursa (job #2050243) | Cod sursa (job #793258) | Cod sursa (job #2895030) | Cod sursa (job #2458577) | Cod sursa (job #1920857)
#include <bits/stdc++.h>
using namespace std;
const int nmax = 1e5 + 10;
int n, m;
int used[nmax], low[nmax], lvl[nmax];
vector < int > g[nmax];
vector < pair < int, int > > st;
vector < vector < int > > ans;
void input() {
scanf("%d %d", &n, &m);
for (int i = 1; i <= m; ++i) {
int x, y;
scanf("%d %d", &x, &y);
g[x].push_back(y);
g[y].push_back(x);
}
}
void get_biconex(pair < int, int > edge) {
vector < int > res;
while (true) {
pair < int, int > curr = st.back(); st.pop_back();
res.push_back(curr.second);
if (curr == edge) break;
}
res.push_back(edge.first);
ans.push_back(res);
}
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.push_back({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() {
printf("%d\n", (int)ans.size());
for (int i = 0; i < (int)ans.size(); ++i, printf("\n"))
for (auto &it: ans[i])
printf("%d ", it);
}
int main() {
freopen("biconex.in","r",stdin);
freopen("biconex.out","w",stdout);
input();
dfs(1);
output();
return 0;
}