TIOJ 2117

2qbingxuan

2024-12-18

殿壬與最大流

https://tioj.ck.tp.edu.tw/problems/2117

Description

$Q \leq 2 \times 10^5$ 次詢問無向圖 $G$ 上面任兩點的最大流（邊權是 $1$）。但是，$G$ 是一張 $N$ 點 $N$ 邊連通圖。

Solution

$N$ 點 $N$ 邊無向連通圖的結構必定是一棵樹加上一條邊，或者也可以描述成一個環上面長出許多子樹。關鍵字是 pseudo tree 或基環樹 / based ring tree。

兩點之間的最大流必定是 $1$ 或 $2$。只有兩個點都在環上的時候才會是 $2$，其他情況都可以只拔掉一條邊就讓兩個點不連通。

要找出哪些點在環上，可以直接 dfs 並把唯一的 backedge 所對應的樹上路徑上的點全部選起來就好。

本題還可以一般化成仙人掌版本，兩個點必須要在同一個環上才會是 $2$，不過點仙人掌的情形也許會比較複雜一點。

AC code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <bits/stdc++.h>
using namespace std;

#define all(x) begin(x), end(x)
#ifdef local
#define safe cerr << __LINE__ << " line " << __LINE__ << " safe\n"
#define debug(a...) debug_(#a, a)
#define orange(a...) orange_(#a, a)
template <typename ...T>
void debug_(const char *s, T ...a) {
  cerr << "\e[1;32m(" << s << ") = (";
  int cnt = sizeof...(T);
  (..., (cerr << a << (--cnt ? ", " : ")\e[0m\n")));
}
template <typename I>
void orange_(const char *s, I L, I R) {
  cerr << "\e[1;32m[ " << s << " ] = [ ";
  for (int f = 0; L != R; ++L)
    cerr << (f++ ? ", " : "") << *L;
  cerr << " ]\e[0m\n";
}
#else
#define safe ((void)0)
#define debug(...) safe
#define orange(...) safe
#endif

using lld = int64_t;

signed main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int N;
  cin >> N;

  vector<vector<int>> g(N);
  for (int i = 0; i < N; i++) {
    int a, b;
    cin >> a >> b;
    --a, --b;
    g[a].emplace_back(b);
    g[b].emplace_back(a);
  }

  vector<int> onCycle(N), pa(N, -1), vis(N);
  int dft = 0;
  auto dfs = [&](auto &self, int i) -> void {
    vis[i] = ++dft;
    for (int j : g[i]) {
      if (!vis[j]) {
        pa[j] = i;
        self(self, j);
      } else if (j != pa[i] && vis[j] < vis[i]) {
        for (int x = i; x != j; x = pa[x])
          onCycle[x] = true;
        onCycle[j] = true;
      }
    }
  };
  dfs(dfs, 0);

  int Q;
  cin >> Q;
  while (Q--) {
    int a, b;
    cin >> a >> b;
    --a, --b;
    if (onCycle[a] && onCycle[b]) {
      cout << 2 << '\n';
    } else {
      cout << 1 << '\n';
    }
  }
}