Pagini recente » Cod sursa (job #3324865) | Cod sursa (job #3199575) | Cod sursa (job #3335392) | Borderou de evaluare (job #3325123) | Cod sursa (job #3340733)
#include <bits/stdc++.h>
std::ifstream fin("biconex.in");
std::ofstream fout("biconex.out");
const int MOD = 1e9 + 7;
const int INF = 1e9 + 5;
const int64_t LONG_INF = static_cast<int64_t>(1e18) + 5;
const int NMAX = 1e5 + 5;
int n, m;
std::vector<int> graph[NMAX];
std::vector<int> biconex_comp[NMAX];
int lvl[NMAX], min_lvl[NMAX], biconex_cnt;
void dfs(int node, int parent, std::stack<int> &st) {
lvl[node] = min_lvl[node] = lvl[parent] + 1;
st.push(node);
for (auto adj : graph[node]) {
if (adj == parent) {
continue;
}
// found back-edge
if (lvl[adj]) {
min_lvl[node] = std::min(min_lvl[node], lvl[adj]);
continue;
}
dfs(adj, node, st);
min_lvl[node] = std::min(min_lvl[node], min_lvl[adj]);
// found articulation point
if (lvl[node] <= min_lvl[adj]) {
// get biconex component
biconex_cnt++;
biconex_comp[biconex_cnt].push_back(node);
int comp_node;
do {
comp_node = st.top();
biconex_comp[biconex_cnt].push_back(comp_node);
st.pop();
} while (comp_node != adj);
}
}
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
fin >> n >> m;
for (int i = 1; i <= m; ++i) {
int x, y;
fin >> x >> y;
graph[x].push_back(y);
graph[y].push_back(x);
}
std::stack<int> st;
for (int i = 1; i <= n; ++i) {
if (!lvl[i]) {
dfs(i, 0, st);
}
}
fout << biconex_cnt << "\n";
for (int i = 1; i <= biconex_cnt; ++i) {
for (auto node : biconex_comp[i]) {
fout << node << " ";
}
fout << "\n";
}
return 0;
}