Pagini recente » Cod sursa (job #896175) | Cod sursa (job #2876321) | Cod sursa (job #2670097) | Cod sursa (job #2086130) | Cod sursa (job #3154539)
#include <iostream>
#include <vector>
#include <stack>
#include <set>
const int MAX_N = 100001;
std::vector<int> adj[MAX_N];
std::vector<std::vector<int>> blockCut;
bool visited[MAX_N];
int depth[MAX_N], low[MAX_N];
std::stack<std::pair<int, int>> s;
void dfs(int u, int d) {
depth[u] = d;
low[u] = d;
visited[u] = true;
for (int v : adj[u]) {
if (!visited[v]) {
s.push(std::make_pair(u, v));
dfs(v, d + 1);
low[u] = std::min(low[u], low[v]);
if (low[v] >= depth[u]) {
//std::cerr << u << " " << v << '\n';
std::set<int> c;
while (s.top().first != u && s.top().second != v) {
c.insert(s.top().first);
c.insert(s.top().second);
s.pop();
}
c.insert(s.top().first);
c.insert(s.top().second);
s.pop();
std::vector<int> convert;
for (int i : c)
convert.push_back(i);
blockCut.push_back(convert);
}
} else {
low[u] = std::min(low[u], depth[v]);
}
}
}
int main() {
freopen("biconex.in", "r", stdin);
freopen("biconex.out", "w", stdout);
int n, m;
std::cin >> n >> m;
for (int i = 0; i < m; i++) {
int u, v;
std::cin >> u >> v;
u--;
v--;
adj[u].push_back(v);
adj[v].push_back(u);
}
dfs(0, 0);
std::cout << blockCut.size() << '\n';
for (auto i : blockCut) {
for (auto j: i)
std::cout << j + 1 << " ";
std::cout << '\n';
}
return 0;
}