Pagini recente » Cod sursa (job #1490591) | Istoria paginii runda/leitentw1/clasament | Cod sursa (job #1752248) | Cod sursa (job #421046) | Cod sursa (job #2818175)
#include <bits/stdc++.h>
#ifdef ONLINE_JUDGE
#define in std::cin
#define out std::cout
#else
std::ifstream in("biconex.in");
std::ofstream out("biconex.out");
#endif
template<typename T, size_t N>
constexpr size_t length_of(T (&)[N]) {
return N;
}
template<typename T>
using Vec = std::vector<T>;
template<typename T, typename U>
using Pair = std::pair<T, U>;
template<typename F>
using Func = std::function<F>;
using i64 = int64_t;
using u64 = uint64_t;
using i8 = char;
using u8 = unsigned char;
template<typename T>
T update_min(T &min, T val) {
return min = std::min(min, val);
}
template<typename T>
T update_max(T &max, T val) {
return max = std::max(max, val);
}
constexpr int N = 1e5 + 1;
struct Graph {
int n;
Vec<int> nodes[N];
void add_edge(int u, int v);
Vec<Vec<int>> biconnected_components();
struct NodeTimes {
int in[N];
int min[N];
} t;
} g;
void Graph::add_edge(int u, int v) {
nodes[u].push_back(v);
nodes[v].push_back(u);
}
Vec<Vec<int>> Graph::biconnected_components() {
Vec<Vec<int>> res;
res.reserve(n);
std::stack<int> dfs_stack;
auto add_component = [&](int from, int to) {
res.emplace_back();
auto &comp = res.back();
while (dfs_stack.top() != to) {
comp.push_back(dfs_stack.top());
dfs_stack.pop();
}
comp.push_back(to);
dfs_stack.pop();
comp.push_back(from);
};
Func<void(int, int)> dfs = [&](int u, int parent) {
static int ct;
t.min[u] = t.in[u] = ++ct;
dfs_stack.push(u);
for (int v : nodes[u]) {
if (t.in[v] == 0) {
dfs(v, u);
update_min(t.min[u], t.min[v]);
if (t.min[v] >= t.in[u]) {
add_component(u, v);
}
} else if (v != parent) {
update_min(t.min[u], t.in[v]);
}
}
};
for (int u = 1; u <= n; ++u) {
if (t.in[u] == 0) {
dfs(u, 0);
}
}
return res;
}
int main() {
int m;
in >> g.n >> m;
for (int i = 0; i < m; ++i) {
int u, v;
in >> u >> v;
g.add_edge(u, v);
}
auto res = g.biconnected_components();
out << res.size() << '\n';
for (auto &comp : res) {
for (auto u : comp) {
out << u << ' ';
}
out << '\n';
}
}