bipolar_orientation.hpp

SECTIONGraph INCLUDEnoya/bipolar_orientation.hpp

把双连通无向图定向成只有一个源和一个汇的无环图，并给出 st 编号。

Complexity: Time: O(V + E). Space: O(V + E).

AC 记录：st_numbering。

跳到代码 · GitHub ↗

Implementation

ReferenceSourceExpanded

当前头文件，省略 include guard；依赖见 #include。

/// @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>> &es, int s,
                    int t) {
  assert(n >= 2);
  assert(0 <= s && s < n);
  assert(0 <= t && t < n && s != t);
  std::vector<std::vector<int>> g(n);
  bool te = false;
  for (auto [a, b] : es) {
    assert(0 <= a && a < n);
    assert(0 <= b && b < n);
    if (a == b) {
      continue;
    }
    g[a].push_back(b);
    g[b].push_back(a);
    te |= (a == s && b == t) || (a == t && b == s);
  }
  if (!te) {
    return {};
  }
  for (auto &adj : g) {
    std::sort(adj.begin(), adj.end());
    adj.erase(std::unique(adj.begin(), adj.end()), adj.end());
  }

  std::vector<int> dfn(n), low(n), fa(n, -1), ord;
  int tim = 0;
  auto dfs = [&](auto &self, int u) -> void {
    dfn[u] = ++tim;
    low[u] = u;
    for (int nxt : g[u]) {
      if (dfn[nxt] == 0) {
        ord.push_back(nxt);
        self(self, nxt);
        fa[nxt] = u;
        if (dfn[low[nxt]] < dfn[low[u]]) {
          low[u] = low[nxt];
        }
      } else if (dfn[nxt] < dfn[low[u]]) {
        low[u] = nxt;
      }
    }
  };
  dfn[s] = ++tim;
  low[s] = s;
  dfs(dfs, t);
  if (tim != n) {
    return {};
  }

  std::vector<int> pre(n, -1), nxt(n, -1), sgn(n, -1);
  nxt[s] = t;
  pre[t] = s;
  for (int u : ord) {
    if (u == t) {
      continue;
    }
    int piv = fa[u];
    if (sgn[low[u]] == -1) {
      int l = pre[piv];
      if (l == -1) {
        return {};
      }
      nxt[l] = u;
      pre[u] = l;
      nxt[u] = piv;
      pre[piv] = u;
      sgn[piv] = 1;
    } else {
      int r = nxt[piv];
      if (r == -1) {
        return {};
      }
      nxt[piv] = u;
      pre[u] = piv;
      nxt[u] = r;
      pre[r] = u;
      sgn[piv] = -1;
    }
  }

  std::vector<int> or1;
  for (int u = s; u != -1; u = nxt[u]) {
    or1.push_back(u);
  }
  if (int(or1.size()) != n || or1.back() != t) {
    return {};
  }
  std::vector<int> pos(n);
  for (int i = 0; i < n; i++) {
    pos[or1[i]] = i;
  }
  for (int i = 1; i + 1 < n; i++) {
    bool hl = false;
    bool hh = false;
    for (int nx1 : g[or1[i]]) {
      hl |= pos[nx1] < i;
      hh |= pos[nx1] > i;
    }
    if (!hl || !hh) {
      return {};
    }
  }
  return or1;
}

} // namespace noya

#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>> &es, int s,
                    int t) {
  assert(n >= 2);
  assert(0 <= s && s < n);
  assert(0 <= t && t < n && s != t);
  std::vector<std::vector<int>> g(n);
  bool te = false;
  for (auto [a, b] : es) {
    assert(0 <= a && a < n);
    assert(0 <= b && b < n);
    if (a == b) {
      continue;
    }
    g[a].push_back(b);
    g[b].push_back(a);
    te |= (a == s && b == t) || (a == t && b == s);
  }
  if (!te) {
    return {};
  }
  for (auto &adj : g) {
    std::sort(adj.begin(), adj.end());
    adj.erase(std::unique(adj.begin(), adj.end()), adj.end());
  }

  std::vector<int> dfn(n), low(n), fa(n, -1), ord;
  int tim = 0;
  auto dfs = [&](auto &self, int u) -> void {
    dfn[u] = ++tim;
    low[u] = u;
    for (int nxt : g[u]) {
      if (dfn[nxt] == 0) {
        ord.push_back(nxt);
        self(self, nxt);
        fa[nxt] = u;
        if (dfn[low[nxt]] < dfn[low[u]]) {
          low[u] = low[nxt];
        }
      } else if (dfn[nxt] < dfn[low[u]]) {
        low[u] = nxt;
      }
    }
  };
  dfn[s] = ++tim;
  low[s] = s;
  dfs(dfs, t);
  if (tim != n) {
    return {};
  }

  std::vector<int> pre(n, -1), nxt(n, -1), sgn(n, -1);
  nxt[s] = t;
  pre[t] = s;
  for (int u : ord) {
    if (u == t) {
      continue;
    }
    int piv = fa[u];
    if (sgn[low[u]] == -1) {
      int l = pre[piv];
      if (l == -1) {
        return {};
      }
      nxt[l] = u;
      pre[u] = l;
      nxt[u] = piv;
      pre[piv] = u;
      sgn[piv] = 1;
    } else {
      int r = nxt[piv];
      if (r == -1) {
        return {};
      }
      nxt[piv] = u;
      pre[u] = piv;
      nxt[u] = r;
      pre[r] = u;
      sgn[piv] = -1;
    }
  }

  std::vector<int> or1;
  for (int u = s; u != -1; u = nxt[u]) {
    or1.push_back(u);
  }
  if (int(or1.size()) != n || or1.back() != t) {
    return {};
  }
  std::vector<int> pos(n);
  for (int i = 0; i < n; i++) {
    pos[or1[i]] = i;
  }
  for (int i = 1; i + 1 < n; i++) {
    bool hl = false;
    bool hh = false;
    for (int nx1 : g[or1[i]]) {
      hl |= pos[nx1] < i;
      hh |= pos[nx1] > i;
    }
    if (!hl || !hh) {
      return {};
    }
  }
  return or1;
}

} // 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>> &es, int s,
                    int t) {
  assert(n >= 2);
  assert(0 <= s && s < n);
  assert(0 <= t && t < n && s != t);
  std::vector<std::vector<int>> g(n);
  bool te = false;
  for (auto [a, b] : es) {
    assert(0 <= a && a < n);
    assert(0 <= b && b < n);
    if (a == b) {
      continue;
    }
    g[a].push_back(b);
    g[b].push_back(a);
    te |= (a == s && b == t) || (a == t && b == s);
  }
  if (!te) {
    return {};
  }
  for (auto &adj : g) {
    std::sort(adj.begin(), adj.end());
    adj.erase(std::unique(adj.begin(), adj.end()), adj.end());
  }

  std::vector<int> dfn(n), low(n), fa(n, -1), ord;
  int tim = 0;
  auto dfs = [&](auto &self, int u) -> void {
    dfn[u] = ++tim;
    low[u] = u;
    for (int nxt : g[u]) {
      if (dfn[nxt] == 0) {
        ord.push_back(nxt);
        self(self, nxt);
        fa[nxt] = u;
        if (dfn[low[nxt]] < dfn[low[u]]) {
          low[u] = low[nxt];
        }
      } else if (dfn[nxt] < dfn[low[u]]) {
        low[u] = nxt;
      }
    }
  };
  dfn[s] = ++tim;
  low[s] = s;
  dfs(dfs, t);
  if (tim != n) {
    return {};
  }

  std::vector<int> pre(n, -1), nxt(n, -1), sgn(n, -1);
  nxt[s] = t;
  pre[t] = s;
  for (int u : ord) {
    if (u == t) {
      continue;
    }
    int piv = fa[u];
    if (sgn[low[u]] == -1) {
      int l = pre[piv];
      if (l == -1) {
        return {};
      }
      nxt[l] = u;
      pre[u] = l;
      nxt[u] = piv;
      pre[piv] = u;
      sgn[piv] = 1;
    } else {
      int r = nxt[piv];
      if (r == -1) {
        return {};
      }
      nxt[piv] = u;
      pre[u] = piv;
      nxt[u] = r;
      pre[r] = u;
      sgn[piv] = -1;
    }
  }

  std::vector<int> or1;
  for (int u = s; u != -1; u = nxt[u]) {
    or1.push_back(u);
  }
  if (int(or1.size()) != n || or1.back() != t) {
    return {};
  }
  std::vector<int> pos(n);
  for (int i = 0; i < n; i++) {
    pos[or1[i]] = i;
  }
  for (int i = 1; i + 1 < n; i++) {
    bool hl = false;
    bool hh = false;
    for (int nx1 : g[or1[i]]) {
      hl |= pos[nx1] < i;
      hh |= pos[nx1] > i;
    }
    if (!hl || !hh) {
      return {};
    }
  }
  return or1;
}

} // namespace noya