bipolar_orientation.hpp¶
Find an st-numbering of a biconnected undirected graph with edge (source,sink), or return an empty vector if the graph is not suitable.
Verified by st_numbering.
把双连通无向图定向成只有一个源和一个汇的无环图，并给出 st 编号。
Implementation¶
#ifndef NOYA_BIPOLAR_ORIENTATION_HPP
#define NOYA_BIPOLAR_ORIENTATION_HPP 1
/// @complexity Time: O(V + E).
/// Space: O(V + E).
#include <algorithm>
#include <cassert>
#include <queue>
#include <utility>
#include <vector>
namespace noya {
/// @brief Find an st-numbering of a biconnected undirected graph with edge
/// (source,sink), or return an empty vector if the graph is not suitable.
inline std::vector<int>
bipolar_orientation(int n, const std::vector<std::pair<int, int>> &edges,
int source, int sink) {
assert(n >= 2);
assert(0 <= source && source < n);
assert(0 <= sink && sink < n && source != sink);
std::vector<std::vector<int>> graph(n);
bool terminal_edge = false;
for (auto [first, second] : edges) {
assert(0 <= first && first < n);
assert(0 <= second && second < n);
if (first == second) {
continue;
}
graph[first].push_back(second);
graph[second].push_back(first);
terminal_edge |= (first == source && second == sink) ||
(first == sink && second == source);
}
if (!terminal_edge) {
return {};
}
for (auto &neighbors : graph) {
std::sort(neighbors.begin(), neighbors.end());
neighbors.erase(std::unique(neighbors.begin(), neighbors.end()),
neighbors.end());
}
std::vector<int> discovery(n), low_vertex(n), parent(n, -1), dfs_order;
int timer = 0;
auto dfs = [&](auto &self, int vertex) -> void {
discovery[vertex] = ++timer;
low_vertex[vertex] = vertex;
for (int next : graph[vertex]) {
if (discovery[next] == 0) {
dfs_order.push_back(next);
self(self, next);
parent[next] = vertex;
if (discovery[low_vertex[next]] < discovery[low_vertex[vertex]]) {
low_vertex[vertex] = low_vertex[next];
}
} else if (discovery[next] < discovery[low_vertex[vertex]]) {
low_vertex[vertex] = next;
}
}
};
discovery[source] = ++timer;
low_vertex[source] = source;
dfs(dfs, sink);
if (timer != n) {
return {};
}
std::vector<int> previous(n, -1), next(n, -1), sign(n, -1);
next[source] = sink;
previous[sink] = source;
for (int vertex : dfs_order) {
if (vertex == sink) {
continue;
}
int pivot = parent[vertex];
if (sign[low_vertex[vertex]] == -1) {
int left = previous[pivot];
if (left == -1) {
return {};
}
next[left] = vertex;
previous[vertex] = left;
next[vertex] = pivot;
previous[pivot] = vertex;
sign[pivot] = 1;
} else {
int right = next[pivot];
if (right == -1) {
return {};
}
next[pivot] = vertex;
previous[vertex] = pivot;
next[vertex] = right;
previous[right] = vertex;
sign[pivot] = -1;
}
}
std::vector<int> order;
for (int vertex = source; vertex != -1; vertex = next[vertex]) {
order.push_back(vertex);
}
if (int(order.size()) != n || order.back() != sink) {
return {};
}
std::vector<int> position(n);
for (int index = 0; index < n; index++) {
position[order[index]] = index;
}
for (int index = 1; index + 1 < n; index++) {
bool has_lower = false;
bool has_higher = false;
for (int next_vertex : graph[order[index]]) {
has_lower |= position[next_vertex] < index;
has_higher |= position[next_vertex] > index;
}
if (!has_lower || !has_higher) {
return {};
}
}
return order;
}
} // namespace noya
#endif // NOYA_BIPOLAR_ORIENTATION_HPP
#include <algorithm>
#include <cassert>
#include <queue>
#include <utility>
#include <vector>
/// @complexity Time: O(V + E).
/// Space: O(V + E).
namespace noya {
/// @brief Find an st-numbering of a biconnected undirected graph with edge
/// (source,sink), or return an empty vector if the graph is not suitable.
inline std::vector<int>
bipolar_orientation(int n, const std::vector<std::pair<int, int>> &edges,
int source, int sink) {
assert(n >= 2);
assert(0 <= source && source < n);
assert(0 <= sink && sink < n && source != sink);
std::vector<std::vector<int>> graph(n);
bool terminal_edge = false;
for (auto [first, second] : edges) {
assert(0 <= first && first < n);
assert(0 <= second && second < n);
if (first == second) {
continue;
}
graph[first].push_back(second);
graph[second].push_back(first);
terminal_edge |= (first == source && second == sink) ||
(first == sink && second == source);
}
if (!terminal_edge) {
return {};
}
for (auto &neighbors : graph) {
std::sort(neighbors.begin(), neighbors.end());
neighbors.erase(std::unique(neighbors.begin(), neighbors.end()),
neighbors.end());
}
std::vector<int> discovery(n), low_vertex(n), parent(n, -1), dfs_order;
int timer = 0;
auto dfs = [&](auto &self, int vertex) -> void {
discovery[vertex] = ++timer;
low_vertex[vertex] = vertex;
for (int next : graph[vertex]) {
if (discovery[next] == 0) {
dfs_order.push_back(next);
self(self, next);
parent[next] = vertex;
if (discovery[low_vertex[next]] < discovery[low_vertex[vertex]]) {
low_vertex[vertex] = low_vertex[next];
}
} else if (discovery[next] < discovery[low_vertex[vertex]]) {
low_vertex[vertex] = next;
}
}
};
discovery[source] = ++timer;
low_vertex[source] = source;
dfs(dfs, sink);
if (timer != n) {
return {};
}
std::vector<int> previous(n, -1), next(n, -1), sign(n, -1);
next[source] = sink;
previous[sink] = source;
for (int vertex : dfs_order) {
if (vertex == sink) {
continue;
}
int pivot = parent[vertex];
if (sign[low_vertex[vertex]] == -1) {
int left = previous[pivot];
if (left == -1) {
return {};
}
next[left] = vertex;
previous[vertex] = left;
next[vertex] = pivot;
previous[pivot] = vertex;
sign[pivot] = 1;
} else {
int right = next[pivot];
if (right == -1) {
return {};
}
next[pivot] = vertex;
previous[vertex] = pivot;
next[vertex] = right;
previous[right] = vertex;
sign[pivot] = -1;
}
}
std::vector<int> order;
for (int vertex = source; vertex != -1; vertex = next[vertex]) {
order.push_back(vertex);
}
if (int(order.size()) != n || order.back() != sink) {
return {};
}
std::vector<int> position(n);
for (int index = 0; index < n; index++) {
position[order[index]] = index;
}
for (int index = 1; index + 1 < n; index++) {
bool has_lower = false;
bool has_higher = false;
for (int next_vertex : graph[order[index]]) {
has_lower |= position[next_vertex] < index;
has_higher |= position[next_vertex] > index;
}
if (!has_lower || !has_higher) {
return {};
}
}
return order;
}
} // namespace noya