bipolar_orientation.hpp¶
给顶点排序，使源在最前、汇在最后，每个中间点的前后都有邻点；要求原图有源汇边，忽略自环并允许重边。
Complexity: Time: \(O(V + E)\). Space: \(O(V + E)\).
Source: maspy
AC 记录：st_numbering。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O(V + E). Space: O(V + E).
#include <cassert>
#include <cstddef>
#include <utility>
#include <vector>
namespace noya {
/// @brief Return a vertex order from source to sink with an earlier and later
/// neighbor at every interior vertex, or {} if no such order exists.
/// Requires n >= 2, distinct valid terminals, and an existing source-sink edge
/// (returns {} without that edge). Ignores loops; parallel edges are allowed.
/// The witness is not canonical and may change when input edges are permuted.
inline std::vector<int>
bipolar_orientation(int n, const std::vector<std::pair<int, int>> &es, int s,
int t) {
assert(n >= 2);
assert(0 <= s && s < n);
assert(0 <= t && t < n && s != t);
if (n == 2) {
for (auto [a, b] : es) {
assert(0 <= a && a < n && 0 <= b && b < n);
if (a != b) return {s, t};
}
return {};
}
std::vector<std::size_t> off(std::size_t(n) + 1);
bool terminal = false;
for (auto [a, b] : es) {
assert(0 <= a && a < n && 0 <= b && b < n);
if (a == b) continue;
++off[a + 1];
++off[b + 1];
terminal |= (a == s && b == t) || (a == t && b == s);
}
if (!terminal) return {};
for (int u = 0; u < n; ++u) off[u + 1] += off[u];
std::vector<int> to(off.back());
auto cur = off;
for (auto [a, b] : es) {
if (a == b) continue;
to[cur[a]++] = b;
to[cur[b]++] = a;
}
std::vector<int> dfn(n), low(n), parent(n, -1), order{s, t};
order.reserve(n);
dfn[s] = 1;
dfn[t] = 2;
low[s] = s;
low[t] = t;
parent[t] = s;
int timer = 2;
// Fix s first and explore from t; low[] stores vertices, not DFS numbers.
auto dfs = [&](auto &self, int u) -> bool {
for (auto i = off[u]; i < off[u + 1]; ++i) {
int v = to[i];
if (dfn[v] == 0) {
parent[v] = u;
dfn[v] = ++timer;
low[v] = v;
order.push_back(v);
if (!self(self, v) || dfn[low[v]] >= dfn[u]) return false;
if (dfn[low[v]] < dfn[low[u]]) low[u] = low[v];
} else if (dfn[v] < dfn[low[u]]) low[u] = v;
}
return true;
};
if (!dfs(dfs, t)) return {};
// All vertices must be reachable in G-s; together with the strict lowpoint
// checks this proves biconnectivity, so no final adjacency certificate is needed.
if (timer != n) return {};
std::vector<int> prev(n, -1), next(n, -1), sign(n, -1);
next[s] = t;
prev[t] = s;
for (std::size_t i = 2; i < order.size(); ++i) {
int u = order[i], p = parent[u];
if (sign[low[u]] < 0) {
int l = prev[p];
if (l == -1) return {};
next[l] = u;
prev[u] = l;
next[u] = p;
prev[p] = u;
sign[p] = 1;
} else {
int r = next[p];
if (r == -1) return {};
next[p] = u;
prev[u] = p;
next[u] = r;
prev[r] = u;
sign[p] = -1;
}
}
order.clear();
for (int u = s; u != -1; u = next[u]) order.push_back(u);
return order;
}
} // namespace noya
// NOYA_BIPOLAR_ORIENTATION_HPP
#ifndef NOYA_BIPOLAR_ORIENTATION_HPP
#define NOYA_BIPOLAR_ORIENTATION_HPP 1
/// @complexity Time: O(V + E). Space: O(V + E).
#include <cassert>
#include <cstddef>
#include <utility>
#include <vector>
namespace noya {
/// @brief Return a vertex order from source to sink with an earlier and later
/// neighbor at every interior vertex, or {} if no such order exists.
/// Requires n >= 2, distinct valid terminals, and an existing source-sink edge
/// (returns {} without that edge). Ignores loops; parallel edges are allowed.
/// The witness is not canonical and may change when input edges are permuted.
inline std::vector<int>
bipolar_orientation(int n, const std::vector<std::pair<int, int>> &es, int s,
int t) {
assert(n >= 2);
assert(0 <= s && s < n);
assert(0 <= t && t < n && s != t);
if (n == 2) {
for (auto [a, b] : es) {
assert(0 <= a && a < n && 0 <= b && b < n);
if (a != b) return {s, t};
}
return {};
}
std::vector<std::size_t> off(std::size_t(n) + 1);
bool terminal = false;
for (auto [a, b] : es) {
assert(0 <= a && a < n && 0 <= b && b < n);
if (a == b) continue;
++off[a + 1];
++off[b + 1];
terminal |= (a == s && b == t) || (a == t && b == s);
}
if (!terminal) return {};
for (int u = 0; u < n; ++u) off[u + 1] += off[u];
std::vector<int> to(off.back());
auto cur = off;
for (auto [a, b] : es) {
if (a == b) continue;
to[cur[a]++] = b;
to[cur[b]++] = a;
}
std::vector<int> dfn(n), low(n), parent(n, -1), order{s, t};
order.reserve(n);
dfn[s] = 1;
dfn[t] = 2;
low[s] = s;
low[t] = t;
parent[t] = s;
int timer = 2;
// Fix s first and explore from t; low[] stores vertices, not DFS numbers.
auto dfs = [&](auto &self, int u) -> bool {
for (auto i = off[u]; i < off[u + 1]; ++i) {
int v = to[i];
if (dfn[v] == 0) {
parent[v] = u;
dfn[v] = ++timer;
low[v] = v;
order.push_back(v);
if (!self(self, v) || dfn[low[v]] >= dfn[u]) return false;
if (dfn[low[v]] < dfn[low[u]]) low[u] = low[v];
} else if (dfn[v] < dfn[low[u]]) low[u] = v;
}
return true;
};
if (!dfs(dfs, t)) return {};
// All vertices must be reachable in G-s; together with the strict lowpoint
// checks this proves biconnectivity, so no final adjacency certificate is needed.
if (timer != n) return {};
std::vector<int> prev(n, -1), next(n, -1), sign(n, -1);
next[s] = t;
prev[t] = s;
for (std::size_t i = 2; i < order.size(); ++i) {
int u = order[i], p = parent[u];
if (sign[low[u]] < 0) {
int l = prev[p];
if (l == -1) return {};
next[l] = u;
prev[u] = l;
next[u] = p;
prev[p] = u;
sign[p] = 1;
} else {
int r = next[p];
if (r == -1) return {};
next[p] = u;
prev[u] = p;
next[u] = r;
prev[r] = u;
sign[p] = -1;
}
}
order.clear();
for (int u = s; u != -1; u = next[u]) order.push_back(u);
return order;
}
} // namespace noya
#endif // NOYA_BIPOLAR_ORIENTATION_HPP
/// @complexity Time: O(V + E). Space: O(V + E).
#include <cassert>
#include <cstddef>
#include <utility>
#include <vector>
namespace noya {
/// @brief Return a vertex order from source to sink with an earlier and later
/// neighbor at every interior vertex, or {} if no such order exists.
/// Requires n >= 2, distinct valid terminals, and an existing source-sink edge
/// (returns {} without that edge). Ignores loops; parallel edges are allowed.
/// The witness is not canonical and may change when input edges are permuted.
inline std::vector<int>
bipolar_orientation(int n, const std::vector<std::pair<int, int>> &es, int s,
int t) {
assert(n >= 2);
assert(0 <= s && s < n);
assert(0 <= t && t < n && s != t);
if (n == 2) {
for (auto [a, b] : es) {
assert(0 <= a && a < n && 0 <= b && b < n);
if (a != b) return {s, t};
}
return {};
}
std::vector<std::size_t> off(std::size_t(n) + 1);
bool terminal = false;
for (auto [a, b] : es) {
assert(0 <= a && a < n && 0 <= b && b < n);
if (a == b) continue;
++off[a + 1];
++off[b + 1];
terminal |= (a == s && b == t) || (a == t && b == s);
}
if (!terminal) return {};
for (int u = 0; u < n; ++u) off[u + 1] += off[u];
std::vector<int> to(off.back());
auto cur = off;
for (auto [a, b] : es) {
if (a == b) continue;
to[cur[a]++] = b;
to[cur[b]++] = a;
}
std::vector<int> dfn(n), low(n), parent(n, -1), order{s, t};
order.reserve(n);
dfn[s] = 1;
dfn[t] = 2;
low[s] = s;
low[t] = t;
parent[t] = s;
int timer = 2;
// Fix s first and explore from t; low[] stores vertices, not DFS numbers.
auto dfs = [&](auto &self, int u) -> bool {
for (auto i = off[u]; i < off[u + 1]; ++i) {
int v = to[i];
if (dfn[v] == 0) {
parent[v] = u;
dfn[v] = ++timer;
low[v] = v;
order.push_back(v);
if (!self(self, v) || dfn[low[v]] >= dfn[u]) return false;
if (dfn[low[v]] < dfn[low[u]]) low[u] = low[v];
} else if (dfn[v] < dfn[low[u]]) low[u] = v;
}
return true;
};
if (!dfs(dfs, t)) return {};
// All vertices must be reachable in G-s; together with the strict lowpoint
// checks this proves biconnectivity, so no final adjacency certificate is needed.
if (timer != n) return {};
std::vector<int> prev(n, -1), next(n, -1), sign(n, -1);
next[s] = t;
prev[t] = s;
for (std::size_t i = 2; i < order.size(); ++i) {
int u = order[i], p = parent[u];
if (sign[low[u]] < 0) {
int l = prev[p];
if (l == -1) return {};
next[l] = u;
prev[u] = l;
next[u] = p;
prev[p] = u;
sign[p] = 1;
} else {
int r = next[p];
if (r == -1) return {};
next[p] = u;
prev[u] = p;
next[u] = r;
prev[r] = u;
sign[p] = -1;
}
}
order.clear();
for (int u = s; u != -1; u = next[u]) order.push_back(u);
return order;
}
} // namespace noya
// NOYA_BIPOLAR_ORIENTATION_HPP