Pagini recente » Cod sursa (job #661716) | Cod sursa (job #1448794) | Cod sursa (job #1082775) | Cod sursa (job #2601484) | Cod sursa (job #3005278)
#include <bits/stdc++.h>
using namespace std;
const string task("biconex");
ifstream fin(task + ".in");
ofstream fout(task + ".out");
const int N = 100000 + 5;
int n, m, vis[N], lma[N], lvl[N];
vector<int> adj[N];
stack<int> st;
vector<vector<int>> cbic;
void dfs(int u, int p) {
vis[u] = 1;
lvl[u] = lma[u] = lvl[p] + 1;
st.push(u);
for (auto v : adj[u]) {
if (v == p) continue;
if (vis[v])
lma[u] = min(lma[u], lvl[v]);
else {
dfs(v, u);
lma[u] = min(lma[u], lma[v]);
if (lma[v] >= lvl[u]) {
vector<int> comp;
while (st.top() != v) {
comp.push_back(st.top());
st.pop();
}
comp.push_back(u);
comp.push_back(v);
cbic.push_back(comp);
st.pop();
}
}
}
}
int main() {
fin >> n >> m;
while (m--) {
int u, v; fin >> u >> v;
adj[u].emplace_back(v);
adj[v].emplace_back(u);
}
for (int i = 1; i <= n; ++i)
if (!vis[i])
dfs(i, 0);
fout << cbic.size() << '\n';
for (auto i : cbic) {
for (auto j : i)
fout << j << ' ';
fout << '\n';
}
}