Pagini recente » Cod sursa (job #1532195) | Cod sursa (job #1200959) | Cod sursa (job #2527787) | Cod sursa (job #1478512) | Cod sursa (job #2365361)
#include <bits/stdc++.h>
using namespace std;
ifstream fi("biconex.in");
ofstream fo("biconex.out");
const int N = 1e5 + 5;
vector<int> g[N];
int lvl[N], low[N];
bool f[N];
vector<vector<int>> bcx;
vector<int> stk;
int n, m;
static void dfs(int u, int far = 0) {
f[u] = true;
lvl[u] = low[u] = lvl[far] + 1;
for (auto v: g[u]) if (v != far && f[v])
low[u] = min(low[u], lvl[v]);
stk.push_back(u);
for (auto v: g[u]) if (!f[v]) {
dfs(v, u);
if (low[v] >= lvl[u]) { // I'm at the top of a biconnected
while (stk.back() != v) {
bcx.back().push_back(stk.back());
stk.pop_back(); }
stk.pop_back();
bcx.back().push_back(v);
bcx.back().push_back(u);
bcx.emplace_back(); }
low[u] = min(low[u], low[v]); } }
int main() {
fi >> n >> m;
for (int u, v, i = 0; i < m; ++i) {
fi >> u >> v;
g[u].push_back(v);
g[v].push_back(u); }
for (int i = 1; i <= n; ++i) if (!f[i]) {
bcx.emplace_back();
dfs(i); }
bcx.pop_back();
fo << bcx.size() << '\n';
for (const auto &i: bcx) {
for (const auto &j: i)
fo << j << ' ';
fo << '\n'; }
return 0; }