Pagini recente » Cod sursa (job #2696962) | Cod sursa (job #3295761)
#include <iostream>
#include <fstream>
#include <vector>
std::ifstream fin("biconex.in");
std::ofstream fout("biconex.out");
const int MAX_N = 100000;
int n, m;
std::vector<int> g[MAX_N + 1];
int tin[MAX_N + 1];
int low[MAX_N + 1];
int tmr;
int stk[MAX_N + 1], sz;
std::vector<std::vector<int>> componente;
void dfs(int node, int dad) {
tin[node] = ++tmr;
low[node] = tin[node];
stk[++sz] = node;
for (auto it : g[node]) {
if (it == dad) continue;
if (tin[it]) {
low[node] = std::min(low[node], tin[it]);
} else {
dfs(it, node);
low[node] = std::min(low[node], low[it]);
if (low[it] == tin[node]) {
std::vector<int> comp;
while (sz > 0 && stk[sz] != it) {
comp.push_back(stk[sz]);
sz--;
}
comp.push_back(it);
sz--;
comp.push_back(node);
componente.push_back(comp);
} else if (low[it] == tin[it]){
sz--;
componente.push_back({node, it});
}
}
}
}
void solve() {
fin >> n >> m;
for (int i = 1; i <= m; i++) {
int u, v;
fin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1, 0);
fout << componente.size() << '\n';
for (auto & it : componente) {
for (int x : it) {
fout << x << ' ';
}
fout << '\n';
}
}
int main() {
solve();
return 0;
}