最短路是圖論最基本的一類問題。
下文記 \(dis_u\) 表示從源點到節點 \(u\) 的最短路，\(n\) 為節點數 \(|V|\)，\(m\) 為邊數 \(|E|\)。
Bellman-Ford 是一種非常暴力的求解最短路的方法（BF 之於 Dijkstra 如同 FF 之於 Dinic）。
稱一輪 鬆弛 為對於每一條邊 \((u, v)\)，用 \(dis_u + w_{u, v}\) 更新 \(dis_v\)。我們斷言每輪至少有一個節點的最短路被更新。鬆弛 \(n - 1\) 輪即可。
正確性證明：設源點為 \(1\)。在 \(1\to u\) 的最短路 \(1\to p_1\to\cdots\to u\) 中，對於每個節點 \(p_i\)，\(1\to p_1\to\cdots\to p_i\) 也一定是 \(1\to p_i\) 的最短路，反證法易證。所以一個節點的最短路一定由另一個節點的最短路擴充套件而來。因為最短路最多有 \(n - 1\) 條邊，而第 \(i\) 輪鬆弛會得到邊數為 \(i\) 的最短路，故至多隻需鬆弛 \(n - 1\) 輪。
該演演算法還可以判斷一張圖上是否存在負環。如果在第 \(n\) 輪鬆弛時仍有節點的最短路被更新，那麼圖存在負環。
演演算法的時間複雜度為 \(\mathcal{O}(nm)\)。
Dijkstra 是基於 貪心 的最短路演演算法，適用於 非負權圖。
稱 擴充套件 節點 \(u\) 為對於 \(u\) 的所有出邊 \((u, v)\)，用 \(dis_u + w_{u, v}\) 更新 \(dis_v\)。
在已經得到最短路的節點中，取出沒有擴充套件過的距離源點最近（即 \(dis\) 最小）的節點並擴充套件。因為沒有負權邊，所以取出的節點的最短路長度單調不降。
如何判斷一個節點已經取到了最短路？實際上不需要判斷，每次取出的節點恰取到了其最短路。根據邊權非負以及 dijkstra 的貪婪演演算法流程，可以通過歸納法與反證法證明這一點。
歸納假設已經擴充套件過的節點 \(p_1, p_2, \cdots, p_{k - 1}\) 在擴充套件時均取到了其最短路。\(p_k\) 為沒有被擴充套件的 \(dis\) 最小的節點。
\(p_k\) 的最短路一定由 \(p_i(1\leq i < k)\) 的最短路擴充套件而來，不可能出現 \(dis(p_i) + w(p_i, p_{k + 1}) + w(p_{k + 1}, p_k) < dis(p_j) + w(p_j, p_k)(1\leq i, j < k)\) 的情況。否則由於邊權非負，\(w(p_{k + 1}, p_k) \geq 0\)，所以 \(dis(p_i) + w(p_i, p_{k + 1}) < dis(p_j) + w(p_j, p_k)\)，即當前 \(dis(p_{k + 1}) < dis(p_k)\)，與 \(dis(p_k)\) 的最小性矛盾。
初始令源點的 \(dis\) 為 \(0\)，假設成立，因此演演算法正確。
取出 \(dis\) 最小的節點的過程可以用優先佇列 priority_queue 維護。每次擴充套件 \(u\) 時，若 \(dis_u + w_{u, v} < dis_v\)，那麼將 \((v, dis_u + w_{u, v})\) 即節點編號和它更新後的 \(dis\) 作為二元組丟進優先佇列。嘗試取出節點時，以 \(dis_u + w_{u, v}\) 為關鍵字取出最小的二元組，則它對應的節點編號就是我們要找的節點。
注意，一個節點可能有多個入邊並多次進入優先佇列。但當它第一次被取出時，得到的一定是最短路。為此，需要記錄 vis[i] 表示一個節點是否被擴充套件過。若當前取出節點已經被擴充套件過，則忽略。也可以判斷是否有當前二元組的第二個元等於第一個元（節點編號）的 \(dis\)，若不等說明當前節點被擴充套件過了。否則複雜度將退化為 \(m ^ 2\log m\)。
演演算法的時間複雜度為 \(\mathcal{O}(m\log m)\)。
P4779 模板題程式碼。
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
const int N = 1e5 + 5;
int n, m, s, dis[N];
vector<pii> e[N];
int main() {
cin >> n >> m >> s;
for(int i = 1; i <= m; i++) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
e[u].push_back(make_pair(v, w));
}
memset(dis, 0x3f, sizeof(dis));
dis[s] = 0;
priority_queue<pii, vector<pii>, greater<pii>> q; // 優先取權值較小的 pair
q.push(make_pair(0, s)); // 注意第一關鍵字要放到前面
while(!q.empty()) {
auto t = q.top();
q.pop();
int id = t.second; // 不要搞反了，編號是 second
if(t.first != dis[id]) continue;
for(auto _ : e[id]) {
int it = _.first, d = t.first + _.second;
if(d < dis[it]) q.push(make_pair(dis[it] = d, it));
}
}
for(int i = 1; i <= n; i++) cout << dis[i] << " ";
return 0;
}
關於 SPFA，___。
SPFA 本質上是佇列優化的 Bellman-Ford。
鬆弛節點 \(x\) 時找到接下來有可能鬆弛的點，即與 \(x\) 相鄰且 最短路被更新的點 並壓入佇列。此外，記錄一個點是否在佇列中，若是則不壓入，可以顯著減小常數。
時間複雜度相比 BF 並沒有差異，仍為 \(\mathcal{O}(nm)\)。在一般圖上效率很高，但是可以被特殊資料卡成平方，所以能使用 dijkstra 時不建議 SPFA。
注意，如果使用 SPFA 求解對等的最短路徑（費用流 EK），當隊頭為目標節點時不能結束演演算法。因為一個節點進入佇列並不等同於它已經取到了最短路。
SPFA 判負環：若一個點 進入佇列 超過 \(n-1\) 次（注意不是 被鬆弛，因為一個節點被鬆弛並不意味著進隊），或 最短路邊數 大於 \(n - 1\)，則整張圖存在負環。對於後者，記錄 \(l_i\) 表示從源點到 \(i\) 的最短路長度，鬆弛時令 \(l_v\gets l_u+1\) 並判斷是否有 \(l_v< n\) 即可。
判入隊次數要慢於最短路長度，因此推薦使用後者。
P3385 模板題程式碼。
#include <bits/stdc++.h>
using namespace std;
const int N = 2e3 + 5;
int n, m, dis[N], len[N], vis[N];
vector<pair<int, int>> e[N];
void solve() {
cin >> n >> m;
for(int i = 1; i <= n; i++) e[i].clear();
for(int i = 1; i <= m; i++) {
int u, v, w;
cin >> u >> v >> w;
e[u].push_back(make_pair(v, w));
if(w >= 0) e[v].push_back({u, w});
}
queue<int> q;
memset(dis, 0x3f, sizeof(dis)); // dis 的初始值需要賦成 0x3f
memset(vis, 0, sizeof(vis)); // 清空 vis =.=
q.push(1), len[1] = dis[1] = 0; // 讀題，從頂點 1 出發 =.=
while(!q.empty()) {
int t = q.front();
q.pop(), vis[t] = 0;
for(auto it : e[t]) {
int d = dis[t] + it.second, to = it.first;
if(d < dis[to]) {
dis[to] = d, len[to] = len[t] + 1;
if(len[to] == n) return puts("YES"), void();
if(!vis[to]) vis[to] = 1, q.push(to);
}
}
}
puts("NO");
}
int main() {
int T;
cin >> T;
while(T--) solve();
return 0;
}
Johnson 演演算法用於解決 帶有負權邊 的 全源最短路經 問題。所謂全源最短路徑問題，就是求解圖上任意兩個點之間的最短路。
Johnson 演演算法的巧妙之處在於為每個點賦予 勢能 \(h_i\)。正如物理意義上的勢能，從一個點出發，到達另一個點，無論走什麼路徑，勢能的總變化量是一定的。物理實際啟發我們將邊 \((u, v)\) 的新權值 \(w'_{u, v}\) 設定為 \(w_{u, v} + h_u - h_v\)。
考慮一條路徑 \(S\to p_1 \to p_2 \to \cdots \to T\)，其原長為
新的長度為
化簡後不難看出 \(L(S\to T) = L'(S\to T) + h_T - h_S\)。對於固定的 \(S, T\)，原圖的路徑對應到新圖上面，長度增加了 \(h_S - h_T\)。這與路徑經過了哪些節點無關，而只與 \(S, T\) 有關。因此，原圖上 \(S\to T\) 的最短路在新圖上 仍為最短路。
接下來考慮求解原問題。
由於負權，我們無法使用 dijkstra 求解最短路。多次 SPFA 或 BF 的時間複雜度不優秀。我們嘗試應用上述分析，合理地為每個點賦權值，從而消去圖上的所有負權邊。
為使 \(w'(u, v) \geq 0\)，只需 \(w(u, v) + h_u \geq h_v\)。這是什麼？三角形不等式！若初始圖中無負環，那麼我們一定可以不斷鬆弛最終得到這樣一個 \(h\)。具體地，初始令所有 \(h\) 等於 \(0\)，然後使用 BF 演演算法進行 \(n - 1\) 輪鬆弛。
鬆弛在 \(n - 1\) 輪後必然結束，否則意味著原圖存在負環，因為上述操作等價於建立虛點 \(0\) 並向所有節點連一條邊權為 \(0\) 的邊，並求出 \(0\to i\) 的最短路 \(h_i\)。
操作結束後，我們更新每條邊的權值 \(w'(u, v) = w(u, v) + h(u) - h(v)\)。根據一開始的分析，得到的新圖與原圖任意兩點間的最短路徑不變，且 沒有負邊權，可以使用 \(n\) 輪 Dijkstra 求解任意兩點間的最短路。
最後不要忘了 將 \(u\to v\) 的最短路加上 \(h_v - h_u\)。
演演算法的時間複雜度為 \(\mathcal{O}(nm\log m)\)。
模板題 P5905 程式碼。
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
const int N = 3e3 + 5;
int n, m, h[N], dis[N];
vector<pii> e[N];
int main() {
cin >> n >> m;
for(int i = 1; i <= m; i++) {
int u, v, w;
cin >> u >> v >> w;
e[u].push_back(make_pair(v, w));
}
for(int i = 1; i <= n; i++) {
bool found = 0;
for(int j = 1; j <= n; j++)
for(auto it : e[j])
if(h[j] + it.second < h[it.first])
found = 1, h[it.first] = h[j] + it.second;
if(i == n && found) puts("-1"), exit(0);
}
for(int i = 1; i <= n; i++) {
long long ans = 0;
for(int j = 1; j <= n; j++) dis[j] = i == j ? 0 : 1e9;
priority_queue<pii, vector <pii>, greater <pii>> q;
q.push(make_pair(0, i));
while(!q.empty()) {
auto t = q.top();
q.pop();
int id = t.second;
if(t.first != dis[id]) continue;
for(auto _ : e[id]) {
int it = _.first, d = t.first + h[id] - h[it] + _.second;
if(d < dis[it]) q.push(make_pair(dis[it] = d, it));
}
}
for(int j = 1; j <= n; j++) ans += 1ll * j * (dis[j] + (dis[j] < 1e9 ? h[j] - h[i] : 0));
cout << ans << endl;
}
return 0;
}
和 johnson 一樣，floyd 也可以解決帶有負權邊的全源最短路徑問題。其名聲遠大於 johnson。
Floyd 演演算法的核心只有四步：列舉 \(k\)，列舉 \(i\)，列舉 \(j\)，用 \(dis(i, k) + dis(k, j)\) 更新 \(dis(i, j)\)。
注意列舉順序，作為中轉點的節點必須在最外層列舉。初始令所有有邊的點對 \((u, v)\) 之間的 \(dis(u, v)\) 等於 \(w(u, v)\)。
正確性證明仍然是歸納法。考慮 \(u\to v\) 的最短路 \(u\to p_1 \to \cdots \to p_k \to v\)。令 \(p_i\) 為 \(p\) 當中最後一個被列舉到的點，若 \(dis(u, p_i)\) 和 \(dis(p_i, v)\) 已經取到最短路，那麼 \(dis(u, v)\) 自然能正確地被更新為最短路。
根據初始化操作，邊界情況 \(u\to v\) 的最短路只有一條邊時 \(dis(u, v)\) 取到最短路 \(w(u, v)\) 成立。由數學歸納法，假設成立，演演算法正確性得證。
演演算法的時間複雜度為 \(\mathcal{O}(n ^ 3)\)。不僅好寫，而且在稠密圖上執行效率高於 johnson，因此 floyd 也是資料規模較小時最短路演演算法的不二之選。
此外，floyd 還可以求傳遞閉包（筆者一直以為傳遞閉包是個動詞，沒想到是名詞）。有向圖 \(G\) 的傳遞閉包定義為 \(n\) 階布林矩陣 \(T\)，滿足 \(T_{i, j}\) 當 \(i\) 可達 \(j\) 時等於 \(1\)，否則為 \(0\)。只需將內層操作改為 \(T_{i, j} \gets T_{i, j} \lor (T_{i, k} \land T_{k, j})\) 即可。
bitset 可以將傳遞閉包的複雜度優化至 \(\dfrac {n ^ 3} w\)。對於稀疏圖，縮點後傳遞閉包可以做到 \(\dfrac {nm} w\)。什麼？這麼簡單的東西你還要程式碼？
一道有趣的題目。
\(\mathcal{O}(m\log m \log k)\) 做法的核心思想是 二進位制分組 後跑最短路。兩個不同的數二進位制必定至少有一位不同，正確性得以保證。在洛谷要開 O2 才能過。
隨機分組也可以，做 \(k\) 次的正確性是 \(1 - \left(\dfrac 3 4 \right) ^ k\)。類似題目如 CF1314 D。
\(\mathcal{O}(m\log m)\) 做法的思想很巧妙。預處理每個特殊城市到點 \(i\) 的最短距離 \(f_i\) 和對應城市 \(fr_i\)，以及點 \(i\) 到所有特殊城市的最短距離 \(g_i\) 和對應城市 \(to_i\)。對於每條邊 \(u\to v\)，若 \(fr_u \neq to_v\)，則用 \(f_u + w_{u, v} + g_v\) 更新答案。正確性證明見 srf 的題解。
程式碼。
答案滿足可二分性，二分 + dijkstra 即可。
時間複雜度 \(n\log n \log c\)。
注意到 \(k\) 很小，跑最短路時記錄當前用了幾條免費邊即可,這叫分層圖最短路。
時間複雜度 \(\mathcal{O}(mk\log(mk))\)。
\(k = 2\) 是 「狼抓兔子」，平面圖最小割轉對偶圖最短路。
\(k > 2\) 的時候也差不多。平面圖轉對偶圖後，最外層會出現 \(k\) 個節點。對於一個節點 \(i\)，設其逆時針方向的射線顏色和順時針方向的射線顏色分別為 \(L_i\) 和 \(R_i\)，取值為 \(0\) 或 \(1\)，表示白或黑。若 \(L_i = R_i\)，那麼 \(i\) 相鄰的兩個射線處於同一連通塊是最優的。因為任何將它們分割開的方案，通過調整使得它們在同一連通塊後代價總會減少。
顯然，\((L_i, R_i)\) 等於 \((0, 1)\) 和 \((1, 0)\) 的節點個數相同。每個 \((0, 1)\) 和每個 \((1, 0)\) 匹配，路徑經過的所有邊兩端顏色不同。因此這樣的匹配方案總能給出一個劃分方案及其代價。
關鍵性質是任意兩點的匹配不會相交，即不會出現 \(a < b < c < d\) 且 \(a\) 匹配 \(c\)，\(b\) 匹配 \(d\)。若相交，則調整法可證不交時不劣。
因此，首先求出所有 \((0, 1)\) 和 \((1, 0)\) 點之間兩兩最短路。求匹配最小代價可以類似括號匹配，破環成鏈後區間 DP，時間複雜度 \(\mathcal{O}(knm\log(nm) + k ^ 3)\)。
程式碼。
經典題。
首先求出 \(1\to n\) 的最短路 \(P = p_0(= 1)\xrightarrow {e_1} p_1 \xrightarrow {e_2} \cdots \xrightarrow {e_L} p_L(= n)\)。設 \(t = (u, v)\)。
當 \(t\notin P\) 時，新的最短路要麼不變，要麼經過這條邊。很顯然，強制經過某條邊 \((u, v)\) 的最短路等於 \(1\) 到 \(u\) 的最短路，加上 \(v\) 到 \(n\) 的最短路，再加上 \(w_t\)；或者交換 \(u, v\) 的地位，兩種情況取個最小值。設 \(1\) 到 \(u\) 的最短路為 \(pre(u)\)，\(v\) 到 \(n\) 的最短路為 \(suf(v)\)，則答案可寫為
當 \(t\in P\) 時，新的最短路要麼是 \(w(P) - w_t + x\)，要麼是強制不經過 \(t\) 的最短路（當 \(x \leq w_t\) 時必然是前者，但是分類討論太麻煩了，不如兩種情況直接取 \(\min\)）。現在唯一的問題轉化為對每條邊 \(t\)，求解 \(L(t)\) 表示強制不經過 \(t\) 的最短路長度。
考慮求出原圖的任意一棵從 \(1\) 和從 \(n\) 開始的最短路樹 \(T_1\) 和 \(T_n\)。需保證這兩棵樹上 \(1\) 與 \(n\) 之間的路徑完全相等，即設 \(P = T_1(1\to n)\)，那麼 \(P\) 應當等於 \(T_n(1\to n)\)。這可以先求出 \(T_1\) 以及對應的 \(P\)，再根據 \(P\) 求 \(T_n\)。顯然，\(pre(u)\) 等於 \(T_1\) 上 \(u\) 的深度，\(suf(v)\) 等於 \(T_n\) 上 \(v\) 的深度。
設 \(pr(u)\) 表示 \(T_1(1\to u)\) 與 \(P\) 的最後一個交點（或者說，\(pr(u)\) 等於 \(T_1\) 上 \(n\) 和 \(u\) 的 LCA），\(su(v)\) 表示 \(T_n(v\to n)\) 與 \(P\) 的第一個交點。換種角度理解，\(pr(u)\) 就是從 \(1\) 開始到 \(u\) 的最短路上，最後一個與從 \(1\) 到 \(n\) 的最短路徑重合的節點，對於 \(su(v)\) 同理。
對於一條不屬於 \(P\) 的邊 \((u, v)\)，我們嘗試強制經過這條邊（兩個方向都要試，以下僅討論一個方向）。對於從 \(u\to v\) 而言，根據上述分析，最短路為 \(T_1(1\to u) \cup (u, v) \cup T_n(v\to n)\)，其長度為 \(C(u, v) = pre(u) + w(u, v) + suf(v)\)（定義 \(C(e)\) 表示強制經過 \(e\) 的最短路）。
容易發現，\(C(u, v)\) 這個數值可以用於更新所有路徑 \(P\) 上從 \(pr(u)\) 到 \(su(u)\) 之間所有邊 \(e_i\) 對應的 \(L(e_i)\)，因為 \(C(u, v)\) 對應的路徑沒有經過這些邊。對於每一條不屬於 \(P\) 的邊，其 \(C\) 值會對一段 \(P\) 上對應的路徑產生貢獻。離線掃描線用 multiset 維護即可求出每個 \(L(e_i)\)。
因此，對於 \(t\in P\) 的情況，答案為 \(\min(w(P) - w_t + x, L(t))\)。
等等？是不是有些不嚴謹？筆者在思考本題時，遇到的一個最大的問題是如何證明對於去掉某條 \(e_i\) 後，新的最短路 \(P'\) 上必然存在一條邊 \(e'_j = (p'_{j - 1}, p'_j)\) 使得 \(e_i\) 在 \(pr(p'_{j - 1})\) 和 \(su(p'_j)\) 之間。這個命題等價於 \(P'\) 上至少存在一條邊 \((u, v)\) 使得 \(1\to u\) 的路徑等於 \(T_1(1\to u)\)，\(v\to n\) 的路徑等於 \(T_n(v\to n)\)，且 \(e_i\) 不在 \(pr(u)\) 和 \(su(v)\) 之間 。其證明過於複雜，略去。詳見 cf1163f - ycx's blog。
程式碼。
和上題一樣的套路。
和上題一樣的套路。
注意到總的修補程式數量很少，所以從初始態能夠到達的態一定不會太多。狀壓 + SPFA 即可。
前置知識：Bellman-Ford 和 已死的 SPFA。
差分約束問題為給出若干形如 \(x_a-x_b\leq c\) 或 \(x_a - x_b \geq c\) 的不等式，求任意一組 \(x\) 的解。
我們發現，只要 \(x_a, x_b\) 同在不等號某一側時符號不同，那麼所有限制均可以寫為 \(x_i + c \geq x_j\)。
三角形不等式 再一次出現。我們從 \(i\to j\) 連一條長度為 \(c\) 的邊，然後再從超級源點 \(0\) 向每個點連長度為 \(0\) 的邊防止圖不連通（或者一開始令所有 \(dis = 0\) 並將所有點入隊），跑最短路，每個點的最短路長度就是一組解。
因為一般這個 \(c\) 有負值（全是非負的話所有數相等不就行了嘛），所以用 Bellman-Ford 或 SPFA 求解最短路。顯然，若出現負環則無解。
時間複雜度 \(\mathcal{O}(nm)\)。模板題 P5960 程式碼如下。
#include <bits/stdc++.h>
using namespace std;
const int N = 5e3 + 5;
int n, m, vis[N], dis[N], len[N];
vector<pair<int, int>> e[N];
int main() {
cin >> n >> m;
for(int i = 1; i <= m; i++) {
int u, v, w;
cin >> u >> v >> w, e[v].push_back(make_pair(u, w));
}
queue<int> q;
for(int i = 1; i <= n; i++) q.push(i), vis[i] = 1;
while(!q.empty()) {
int t = q.front();
q.pop(), vis[t] = 0;
for(auto it : e[t]) {
int to = it.first, d = dis[t] + it.second;
if(d < dis[to]) {
dis[to] = d, len[to] = len[t] + 1;
if(len[to] == n) puts("NO"), exit(0);
if(!vis[to]) q.push(to), vis[to] = 1;
}
}
}
for(int i = 1; i <= n; i++) cout << dis[i] << " ";
return 0;
}
一般而言差分約束系統的解沒有 「字典序」 這個概念，因為我們只對變數之間的差值進行約束，而變數本身的值可以隨著某個變數取值的固定而固定，所以解的字典序可以趨於無窮大或無窮小。
字典序的極值建立於變數有界的基礎上。不妨設我們希望求出當限制 \(x_i\leq 0\) 時，整個差分約束系統的字典序的最大值。注意到 \(x_i \leq 0\) 可以看成三角形不等式 \((x_0 = 0) + 0 \geq x_i\)，所以我們建立虛點 \(0\)，將其初始 \(dis\) 賦為 \(0\)，並向其它所有變數連權值為 \(0\) 的邊（這等價於一開始令所有點入隊且 \(dis = 0\)）。
求解差分約束系統時，我們使用了三角形不等式，將其問題轉化為最短路問題。這給予它很好的性質：我們通過 SPFA 求得的一組解，恰為字典序最大解。
首先，讓我們明確，對於一條從 \(u\to v\) 的邊權為 \(w(u, v)\) 的邊，它的含義為限制 \(x_u + w(u, v) \geq x_v\)。
考慮 \(0\) 到每個節點的最短路樹。對於樹上每條邊均滿足 \(x_i + w(i, j) = x_j\)。若 \(x_i + w(i, j) > x_j\)，那麼整張圖還可以繼續鬆弛，若 \(x_i + w(i, j) < x_j\)，說明 \(j\) 的最短路不是由 \(i\) 繼承而來，因此 \((i, j)\) 必然不會作為樹邊出現。
這說明樹上的 \(x_i + w(i, j) \geq x_j\) 的限制已經取滿，取到了等號（\(x_j\) 不能再大了，再大就破壞了限制），每個變數都取到了其理論上界，自然就得到了字典序最大解。
對於字典序最小解，我們限制 \(x_i \geq 0\)。因此所有節點向 \(0\) 連邊 \(w(i, 0) = 0\)。字典序最小即字典序最大時的相反數。因此，考慮將所有變數取反，那麼限制也要全部取反，體現為將圖中所有邊（包括所有新建的邊 \(i\to 0\)）的 方向（而不是邊權）取反。然後求字典序最大解，再取相反數即可。
好題。
轉換思路，與其設定邊權使路徑長度相等，不如設定路徑長度去擬合邊權的限制。
設 \(d_i\) 為 \(1\to i\) 的最短路，我們只需保證對於所有邊 \((u,v)\) 有 \(w_{u,v}=d_v-d_u\) 即可使任意一條簡單路徑長相等。於是 \(1\leq d_v-d_u\leq 9\)，轉化為 \(d_u+9\geq d_v\) 與 \(d_v-1\geq d_u\)，差分約束求解即可。注意不在 \(1\to n\) 的任意一條路徑上的邊沒有用，這些邊不應計入限制，隨便標權值。
神題。
構造題可以考慮調整法。
首先我們固定第一行第一列全都為 \(0\)，可以僅根據 \(b\) 的限制推出剩下來整個矩陣 \(a_{i,j}\)。注意到對矩陣第 \(i\) 行的每個數進行 \(-r_i,+r_i,-r_i,+r_i,\cdots\) 操作後，仍然滿足 \(b\) 的限制，列同理。因此我們設將 \(a_{i,j}\) 加上 \((-1)^jr_i+(-1)^ic_j\)，那麼有 \(0\leq a_{i,j}+(-1)^jr_i+(-1)^ic_j\leq 10^6\)。不過這樣當 \(i,j\) 奇偶性相同時 \(r_i,c_j\) 前的符號相同，出現 和約束，這是無法處理的。
我們希望對於每一行，任意兩個相鄰的位置的 \(r_i\) 的係數相反。對於每一列同理。因此考慮 黑白染色，得到係數 \((-1)^{i + j + 1} r_i + (-1) ^ {i + j} c_j\)。不難發現 \(r_i\) 與 \(c_j\) 前符號一定不同且滿足限制，可以使用差分約束求解，時間複雜度 \(\mathcal{O}(Tnm(n + m))\)。
題目有些卡常，注意常數。SPFA 判最短路長度而不是入隊次數會跑得快一些。
程式碼。
化乘法為加法不難想到取對數，考慮對沒有女裝的限制建出差分約束圖，若出現負環則一定有人女裝。對於固定分數的人 \(i\)，讓 \(0, i\) 之間互相連邊權分別為 \(\log x_i\) 和 \(-\log x_i\) 的邊即可。
套一個二分，時間複雜度 \(\mathcal{O}(ns\log V)\)。
考慮將 \(0\) 看做 \(1\)，\(1\) 看做 \(-1\)，那麼問題的限制是差分約束的形式。
對於限制 \(L - 1, R\)，互相連長度為 \(0\) 的邊。
對於相鄰的兩個位置 \(i - 1\) 和 \(i\)，題目要求 \(|v_i - v_{i - 1}| = 1\)。看似沒有辦法描述。當限制變為 \(|v_i - v_{i - 1}|\leq 1\) 時，我們可以在 \(i\) 和 \(i - 1\) 之間互相連長度為 \(1\) 的邊，並且最大化 \(v\) 的字典序（差分約束本身自帶字典序極值性質）。
我們驚訝地發現，在保證字典序最大的情況下，不可能出現 \(v_i = v_{i - 1}\) 的情況。模擬最短路的過程，我們可以證明每個 \(v_i\) 的奇偶性是固定的，並且相鄰兩個 \(v\) 的奇偶性一定不同：\(0\) 邊連線的兩個點的下標奇偶性相同（題目保證了這一點），\(1\) 邊則奇偶性不同。
整個過程可以想象成，將一些位置初始加入集合 \(S\)，表示它們的 \(v\) 值為 \(0\)。每次考慮增加當前的 \(v\) 值 \(cur\)，並將 \(S\) 的極長連續段向左向右擴充套件，新擴充套件的位置的 \(v\) 值就等於 \(cur\)。這是因為，考慮 \(v_{l - 1} = v_{r + 1} = c\) 且 \([l, r]\) 的 \(v\) 值還沒有確定。我們希望最大化 \(v\) 的字典序，自然 \(v_l = c + 1\)，為此，\(v_r\) 也必須等於 \(c + 1\)，這樣才能讓 \([l, r]\) 這一段的字典序最大，否則我們從 \(l\) 開始的上升段會變短。感性理解一下，我們希望將上升段儘量往前放，而當兩端 \(v\) 值已經固定相等時，一個上升段必須對應一個下降段，所以為了把所有上升段堆到最前面，我們不得不在最後放一個下降段。
這題思想還是挺高妙的，雖然是差分約束但是形式很新穎，需要猜一些性質（或者說，不要被固有思維所限制）才能得到最終解法。
邊權只有 \(0/1\)，考慮 01 BFS，時間複雜度 \(\mathcal{O}(n + m)\)。
若為了避免出現 \(|v_i - v_{i - 1}| = 1\) 的限制而單純求字首和得到 \(v\)，我們會建出帶有負權邊的差分約束網路。用 SPFA 求解會 TLE。
程式碼。
很好，限制非常差分約束。建出圖來，先跑一遍負環判無解。但如何滿足不同的 \(t\) 值數量最大呢？差分約束顯然無法解決這樣的問題。然後就不會了（大霧）。
首先強連通分量縮點（具體見 5.2 小節），不同 SCC 之間獨立，因為我們可以將兩個 SCC 之間的距離拉得任意遠。而一個 SCC 內部的答案就是任意兩點最短路徑的最大值 \(+1\)：使最短路距離增加的只有一類邊，而一類邊的 邊權只有 \(1\)，因此若 \(u\to v\) 的最短路徑為 \(w\)，那麼從 \(u\to v\) 的路徑上所有點必然取遍了 \(t_u\sim t_{v}\) 這 \(w+1\) 個值。
因為圖是稠密圖，因此使用 floyd 演演算法求解任意兩點之間的最短路。答案即每個 SCC 的答案之和。
時間複雜度三方。
非常經典的最小生成樹演演算法，基礎中的基礎。
貪心地將所有邊按照邊權從小到大排序並依次列舉每一條邊，如果當前邊兩端點不連通則加入該邊。連通性用並查集維護。時間複雜度 \(\mathcal{O}(m\log m)\)。
正確性考慮反證法，如果存在一條邊 \((u, v)\) 使得 \((u, v)\notin T\) 且在加入 \((u, v)\) 後 \(T\) 上形成的環當中 \(w(u, v)\) 不是最大權值，那麼斷掉權值最大的邊可以得到一棵更小的生成樹 \(T'\)。但這與貪心策略矛盾，因為 \((u, v)\) 一定在被斷掉的這條邊之前被列舉到並加入 \(T\)。
kruskal 重構樹見 簡單樹論 Part 1，簡單概括一下就是通過在並查集合並時新建虛點從而維護合併關係。
稍微瞭解一下。
維護 \(V, E\)，每次找到 \(\notin E\) 且一端 \(\in V\) 且另一端 \(\notin V\) 的權值最小的邊 \((u, v)\)，並將 \(v\) 加入 \(V\)，\((u, v)\) 加入 \(E\)。初始 \(V\) 可以包含任意一個節點。
另一種理解方式是維護每個節點的權值 \(c_v\) 表示從 \(v\) 出發的所有邊 \((v, u)\) 當中，使得 \(u\in V\) 的最小權值。每次取出權值最小的點加入 \(V\)，將最小生成樹邊權加上 \(c_v\)，並利用 \(v\) 的所有出邊更新剩下來不在 \(V\) 當中所有點的權值。
「取出權值最小的點」 這一過程可以類似 dijkstra 演演算法，通過優先佇列實現。因此，演演算法的時間複雜度為 \(\mathcal{O}(m\log m)\)。
boruvka 求解最小生成樹的方法較為神奇。
考慮若干個點，對於每個點而言，如果想要使得它有邊相連，那麼與它相鄰當中的邊權最小的邊必然入選。這一點通過反證法可以證明。
因此，我們對於每個點，求出與它相連的邊權最小的邊。將所有這些邊加入最小生成樹當中。除去至多 \(\dfrac n 2\) 條重邊，每條邊會使連通塊個數 \(-1\)，因此一次這樣的過程可以使連得通塊個數嚴格減少一半。這樣，對剩餘連通塊繼續上述過程至多 \(\log_2 n\) 輪即可求得 MST。注意，在選擇邊權最小的邊時，不能選擇兩端已經在同一連通塊的邊。
演演算法的時間複雜度為 \(\mathcal{O}(m\log n)\)。
Boruvka 在解決某類最小生成樹問題上非常有用。它形如給定一張 \(n\) 個點的完全圖，兩點之間的資訊可以通過某種計算得出。\(n\) 一般在 \(10 ^ 5\) 級別。
首先 kruskal 求出最小生成樹，然後列舉所有邊 \((u,v)\)，用它替換最小生成樹上 \(u,v\) 之間權值最大或 嚴格 第二大的邊即可。需要嚴格第二大是因為最大值可能和 \(w_{u, v}\) 相等。時間複雜度線性對數。
程式碼。
Boruvka 的有趣應用。
根據互斥或和最小值不難想到對 \(a_i\) 建出 01 Trie。對於 01 Trie 上某個狀態 \(p\) 的子樹所包含的所有節點 \(V_p\)，顯然它們內部之間已經連通，因為 \(V_p\) 跨過該狀態向其它狀態 \(q\) 所表示的節點 \(V_q\) 連邊的代價大於在 \(V_p\) 內部連邊的代價。這是因為跨過連邊時，根據互斥或的性質，代價在 \(p\) 對應位或其高位有值，但內部連邊時 \(p\) 對應位及其高位沒有值。
因此，考慮計算答案。若 \(p\) 的左右兒子均有節點，那麼需要在 \(V_{ls_p}\) 和 \(V_{rs_p}\) 之間連一條邊使得 \(V_p\) 連通。列舉 \(V_{ls_p}\) 當中所有權值 \(v\) 並求出 \(rs_p\) 的子樹中與 \(v\) 互斥或和最小的權值 \(u\)（01 Trie 基本操作），那麼 \(\min u\oplus v\) 即為連邊代價。
由於一個節點最多作為 \(ls_p\) 被列舉 \(\log V\) 次，所以即使不啟發式合併，時間複雜度也是嚴格 \(n\log ^ 2 V\)。使用啟發式之後可以將一個 \(\log V\) 變成 \(\log n\)，其實沒啥用。
程式碼。
以下兩章內容均與 tarjan 演演算法有關。Tarjan 老爺子真是神。
無向圖和有向圖的連通性是圖論重要的一部分。
無向圖連通性的相關術語有 割點 和 割邊（橋）。
兩者的定義十分類似，分別是刪去後 使連通分量個數增加 的節點或邊，且它們都是 無向圖 上的定義。顯然，一個孤立點或一張僅有一條邊構成的無向圖唯二的端點都不是割點，但後者唯一的邊是割邊。
注意百度百科上將割邊定義在無向連通圖上。這是不嚴謹的。非連通圖的割邊為它的每個連通分量的割邊的並。
與割點相對應的概念是 點雙連通圖，定義為 不存在割點 的 無向連通 圖。根據割點的定義，孤立點和由一條邊連線的點對均視作點雙連通圖。一張圖的極大點雙連通子圖稱為 點雙連通分量（V-BCC）。
與割邊相對應的概念是 邊雙連通圖，定義為 不存在割邊 的 無向連通 圖。根據割邊的定義，孤立點是邊雙連通圖，但由一條邊連線的點對不是邊雙連通的。一張圖的極大邊雙連通子圖稱為 邊雙連通分量（E-BCC）。
由於 「不存在割邊」 意味著對於任意兩個不同節點 \(u\) 和 \(v\)，它們之間不存在必經邊。因此，刪去任意一條 \(u\to v\) 的路徑後，\(u, v\) 仍然連通。這說明任意一條邊屬於 至少一個簡單環（這裡，簡單環定義為不經過重複的 邊 的環）。同理，若每條邊至少屬於一個簡單環，容易證明該圖邊雙連通。我們得到了一張無向連通圖是邊雙連通圖的等價判定：任意一條邊屬於至少一個簡單環。
縮點 是 OI 界常見演演算法，簡單地說就是將某種型別的連通分量根據等價性或獨立性縮成一個點，原來連線兩個不同連通分量的邊變成了連線它們縮點後形成的兩個點。根據連通分量的型別不同，縮點可分為無向圖上的邊雙連通分量縮點，點雙連通分量縮點，以及將在第五章介紹的有向圖上的強連通分量（SCC）縮點。
E-BCC 和 V-BCC 縮點後均可以得到一棵樹，而 SCC 縮點後得到了一張有向無環圖 DAG。
接下來介紹 tarjan 演演算法求割點的方法。
筆者預設讀者已經瞭解 dfs 樹與 dfs 序，此處不再贅述。做一個說明，
筆者主要希望提出一種新的理解 tarjan 演演算法的方式。因為網上眾多部落格講解該演演算法的時候，low 陣列彷彿憑空出現，抽象的定義讓很多初學者摸不著頭腦，而從提出問題到解決問題這樣一個邏輯鏈的不完整性（甚至不存在，比如說 「為什麼要設計 low 陣列」）讓我們無法感受到究竟是怎樣的靈感促使了這一演演算法的誕生。我們不僅要學演演算法，更要汲取演演算法的思維方式。
定義一個節點 \(x\) 的子樹表示該節點在 dfs 樹上的子樹，包含節點本身，記作 \(T(x)\)。
以下討論均基於 \(x\) 不為當前連通分量的 dfs 樹的根節點。
對於 \(T(x)\)，若其中存在節點 \(y\in T(x)\) 滿足 \(y\) 不經過 \(x\) 能到達的所有點都被困在 \(T(x)\) 內，則 \(x\) 是割點，這是因為刪掉 \(x\) 後 \(y\) 和 \(T(x)\) 外的節點（由於 \(x\) 不是根，所以 \(T(x)\) 外的節點存在）不連通，連通分量個數增加；反之每個 \(y\) 都與 \(T(x)\) 外連通，所以整個連通分量仍然連通（不會新產生連通分量）。那麼怎麼表示 「不經過 \(x\) 能到達的所有點被困在 \(T(x)\) 內」 呢？
考慮在 dfs 序對應的 時間戳 dfn 上做手腳。應用 動態規劃 的思想：注意到 \(T(x)\) 內所有點的 dfn \(d_y(y\in T(x))\) 都不小於 \(d_x\)，所以設計狀態 \(f_x\) 表示 \(x\) 僅經過一條非樹邊 所能到達的節點的 dfn 的最小值（注意這與一般 tarjan 演演算法的狀態設計不同，即 \(f\) 並不是 low 陣列）。
為什麼是 「僅經過一條非樹邊」：由於 一個割點可能存在於多個環中，對於處在一個 「8」 字形結構最底部的節點 \(y\) 來說，它可以通過一條非樹邊上翻到結構中間的節點 \(x\)，然後再走一條非樹邊上翻到結構頂部的節點 \(u\)，這樣在求 \(x\) 是否是割點的時候就不合法了，因為 \(f_y\) 被 只有經過 \(x\) 才能到達的點 \(u\) 更新，不符合我們一開始 「不經過 \(x\)」 的假設。而只經過一條非樹邊至少保證了我們求到的 \(f_y\) 是 \(y\) 不需要經過中間點能夠直接到達的節點的 dfn 最小值。
另外插一句，這其實也說明了為什麼對於 \(u\) 的已經存取過且在棧中的鄰居 \(v\)，我們用 dfn[v] 而非 low[v] 更新 low[u]。
考慮 \(x\) 在 dfs 樹上的所有兒子 \(y_1, y_2, \cdots, y_c\)，按存取順序排列。不存在 \(y_i\neq y_j\) 使得它們的子樹之間有連邊，否則在 dfs 的過程中，不妨設 \(i < j\)，存取 \(y_i\) 的子樹時就可以直接存取到 \(y_j\) 的子樹，所以 \(y_j\) 在存取 \(y_i\) 時被存取，與 \(y_j\) 是 \(x\) 在 dfs 樹上的兒子矛盾。這說明 \(x\) 的各個兒子之間的 獨立性。換句話說，任何非樹邊連線的兩個點在 dfs 樹上一定呈祖先後代關係。這是無向圖上 tarjan 演演算法正確性的重要保障。讀者需要充分理解這一性質，下文將重複出現。
同時，由於 \(T(y_i)\) 內部是連通的，所以刪去 \(x\) 時 \(T(y_i)\) 內部每個節點與 \(T(x)\) 外的連通性相同。也就是說，要麼 \(T(y_i)\) 所有節點均與 \(T(x)\) 外連通，要麼均不連通。這說明 \(x\) 的某個兒子的子樹 \(T(y_i)\) 內部節點的 等價性。
因此，對於 \(x\) 的每個兒子 \(y_i\)，若 \(T(y_i)\) 內部 存在 一個點使得它能夠不經過 \(x\) 就到達 \(T(x)\) 外的節點，那麼刪掉 \(x\) 後 \(T(y_i)\) 就和 \(T(x)\) 外連通。我們希望 存在 \(y_i\) 使得它 不滿足 這樣一個條件。
先考慮用我們已知的資訊描述 「\(T(y_i)\) 內部存在一個點 \(p\) 使得它不經過 \(x\) 就可以到達 \(T(x)\) 外的節點」。若存在 \(p\in T(y_i)\) 使得存在一條 不經過 \(x\) 的路徑 \(p\to p_1 \to p_2 \to \cdots \to p_c \to q\)，滿足 \(q\) 為路徑上第一個 \(T(x)\) 外的節點（根據獨立性，\(p\) 和 \(p_i\) 均在 \(T(y_i)\) 內），那麼 \(p_c\) 能夠通過一條非樹邊跳出 \(T(x)\)。
這意味著若存在 \(p\in T(y_i)\) 使得它不經過 \(x\) 可以到達 \(T(x)\) 外的節點，那麼考慮它 第一次 到達 \(T(x)\) 外某個節點 \(q\) 的不經過 \(x\) 的路徑，最後一步使得它從 \(T(y_i)\) 內跳到了 \(T(x)\) 外。因為 \(q\) 在 \(x\) 之前被存取過了（否則 \(q\) 在存取 \(y_i\) 時成為 \(T(y_i)\) 的一個節點），所以 \(d_q < d_x\)。這意味著必然存在對應的 \(p_c\in T(y_i)\) 使得 \(f_{p_c} < d_x\)。
反之，若存在 \(p\in T(y_i)\) 使得 \(f_p < d_x\)，那麼顯然 \(T(y_i)\) 記憶體在一個點使得它不經過 \(x\) 可以到達 \(T(x)\) 外的節點。\(p\) 就是一個這樣的節點。
這樣，我們就證明了判定 \(x\) 是割點的法則：當且僅當 存在一條 樹邊 \(x\to y\)，使得 \(y\) 子樹內 不存在 節點 \(u\) 使得 \(f_u < d_x\) 時，\(x\) 是割點。這等價於對於所有 \(u\in T(y)\) 均有 \(f_u \geq d_x\)，即 \(\min f_u \geq d_x\)。
為此，我們只需再記錄一個陣列 \(g_x\) 表示 \(x\) 的子樹內所有節點 \(u\in T(x)\) 的 \(f_u\) 的最小值，即可線上性時間內判斷每個節點是否是割點。
由於 \(f_u\) 等於 \(u\) 在 dfs 樹上所有 返祖邊 \((u, v)\) 對應的 \(d_v\) 的最小值與本身的 dfn 取 \(\min\)（\(v\) 不應是 \(u\) dfs 樹上的父親，因為這意味著 \((u, v)\) 是 樹邊，如果忽略這一點，那麼在求解割點時 不會 影響結果（判定是 \(\min f_u\geq d_x\)，有等號），但求解割邊時會使判斷錯誤（判定是 \(\min f_u > d_x\)，無等號）），即 \(f_u = \min\left(d_u, \min\limits_{v\in \mathrm{ancestor}(u) \land (u, v) \in E} d_v\right)\)，而 \(g_u = \min\limits_{v \in T(x)} f_v\)，根據 樹形動態規劃，即 \(g_u = \min\left(f_u, \min\limits_{v\in \mathrm{son}(u)} g_v\right)\)。
綜上，我們推得
而 \(g_u\) 恰好代表了 \(u\) 的 low 陣列。
三個由逗號分隔的式子分別對應了：
low[u] 初始化為 dfn[u]。dfn[v] 更新 low[u]。因為是無向邊，所以對於任意 \((u, v) \in E\)，只要 \(v\) 在此之前已經被存取過了，那麼 \(v\) 在 dfs 樹上一定是 \(u\) 的祖先（考慮反證法，若不成祖先後代關係，對 \(\mathrm{lca}(u, v)\) 應用子樹獨立性即可推出矛盾）。low[v] 更新 low[u]。這就是大名鼎鼎的 tarjan 演演算法。
別忘了還有 \(x\) 為根節點的情況。
此時，若 \(x\) 在 dfs 樹上有超過一個兒子，那麼根據子節點的獨立性，去掉 \(x\) 後各兒子子樹不連通使得連通塊個數增加，所以 \(x\) 為割點。反之容易證明 \(x\) 不是割點。
綜上，使用 tarjan 演演算法求解有向圖 \(G\) 上所有割點的時間複雜度為 \(\mathcal{O}(n + m)\)。模板題 P3388 程式碼如下。
筆者再次強調，以下程式碼僅在求解割點時正確。求解割邊需要進行額外的特判，這將在下一小節中提到。原因在上文已經分析過。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, m, root, dn, dfn[N], low[N], cnt, buc[N];
vector<int> e[N];
void dfs(int id) {
dfn[id] = low[id] = ++dn;
int son = 0;
for(int it : e[id]) {
if(!dfn[it]) {
son++, dfs(it), low[id] = min(low[id], low[it]);
if(low[it] >= dfn[id] && id != root) cnt += !buc[id], buc[id] = 1;
}
else low[id] = min(low[id], dfn[it]);
}
if(son >= 2 && id == root) cnt += !buc[id], buc[id] = 1;
}
int main() {
cin >> n >> m;
for(int i = 1, u, v; i <= m; i++) cin >> u >> v, e[u].push_back(v), e[v].push_back(u);
for(int i = 1; i <= n; i++) if(!dfn[i]) root = i, dfs(i);
cout << cnt << endl;
for(int i = 1; i <= n; i++) if(buc[i]) cout << i << " ";
return 0;
}
Tarjan 演演算法求割邊的思路和求解割點的思路差不多。
嘗試探究一條邊是割邊的充要條件。
首先，如果一條邊是非樹邊，那麼割掉它顯然不影響連通性，因為樹邊使得整張圖連通。因此，\(e = (u, v)\) 是割邊的 必要條件 是 \(e\) 為樹邊。
不妨設 \(v\) 是 \(u\) 的子節點。割掉 \(e\) 後若整張圖不連通，那麼一定是 \(T(v)\) 和 \(T(v)\) 以外的部分不連通。這說明 \(T(v)\) 內部所有節點必須跨過 \(e\) 才能到達 \(T(v)\) 外，即 \(e\) 是溝通 \(T(v)\) 內外的 橋。
考慮如何快速判斷這種情況。根據求解割點的經驗，不難發現 \(e\) 為割邊等價於 \(g_v > d_u\)，即 low[v] > dfn[u]。相較於割點判定法則，沒有等號的原因是此時我們刪去的是邊而非節點，所以只要子樹能繞過 \(e\) 到達 \(T(v)\) 以外的部分，包括 \(u\) 本身，那麼 \(e\) 就不是割邊。根據子樹獨立性，這意味著子樹通過一條非樹邊能夠到達 \(u\) 或其祖先。又因為時間戳的性質（祖先的時間戳小於後代的時間戳），故有該判定法則。
注意，求解割邊時有個小細節，就是判斷返祖邊。
一個簡陋的想法是 dfs 時記錄父親，若當前邊 \((u, v)\) 指向當前節點的父親（\(v = fa(u)\)），那麼跳過這條邊。這樣有個問題，就是當出現 重邊 時會錯誤，因為我們會將樹邊的重邊也判為樹邊。
解決方法是額外記錄邊的編號。對於 vector 存圖而言，我們在 push_back 當前邊指向的節點時，還要將當前邊的編號一併壓進去。對於鏈式前向星而言，技巧是 成對變換：初始令 \(cnt = 1\)，這樣一來，每條邊及其反邊在鏈式前向星中儲存的編號分別為 \(2\) 和 \(3\)，\(4\) 和 \(5\)，以此類推。這樣，給當前邊編號互斥或 \(1\) 即可得到反邊編號。
綜上，dfs 時記錄當前節點 \(u\)，以及從 \(fa(u)\) dfs 下來時經過的邊的編號 \(id_e\)，那麼對於 \(u\) 的所有出邊 \(e = (u, v)\)，只需判斷 \(e\) 是否等於 \(id_e\)（vector）或者 \(id_e\oplus 1\)（鏈式前向星）即可判斷 \(e\) 是否為樹邊，從而決定是否要忽略掉當前邊。
演演算法的時間複雜度為 \(\mathcal{O}(n + m)\)。
給出另一種求解割邊的方法。
根據子樹的獨立性，所有非樹邊 \(ne\) 連線的兩個端點 \((u, v)\) 一定具有祖先後代關係。這說明在 dfs 樹 \(T\) 上 \(u, v\) 之間是一條豎直的鏈。
因此，求出原圖 \(G\) 的任意一棵生成樹 \(T\)，對於不在 \(T\) 上的邊 \((u, v)\)，將 \(u, v\) 之間所有邊標記為非樹邊即可。可以通過樹上差分實現。
演演算法的時間複雜度為 \(\mathcal{O}(n + m)\)。
求解邊雙連通分量是非常容易的。
容易證明，對於一張無向連通圖 \(G\)，若 \(e\) 為其割邊，那麼對於 \(G\) 的任意子圖 \(G' = (E', V) \subseteq G\)，若 \(e\in E'\)，則必然有 \(e\) 為 \(G'\) 的割邊。
刪去 \(G\) 的所有割邊，可以得到若干連通塊。由於所有割邊均被刪去，所以這些連通塊必然是邊雙連通圖。因此，它們就是原圖的 E-BCC。
接下來介紹邊雙連通分量縮點的方法。
先通過一遍 tarjan 演演算法找到所有割邊，再 dfs 找出所有邊雙連通分量是可行的，但是太麻煩了。我們希望一遍 dfs 就可以做到求解割邊 + 找出所有邊雙連通分量。為此，我們需要對 tarjan 演演算法進行一些改進。
具體地，我們維護一個 棧 \(S\)，表示已經存取過的，還沒有形成完整的連通分量 的所有節點。每次 dfs 進入一個節點時，先將其壓入棧內。這一步驟出現在各種連通分量的縮點演演算法中。
設當前節點為 \(u\)，\(v\) 為當前遍歷到的 \(u\) 的（在 dfs 樹上的）子節點。若 \((u, v)\) 被判定為割邊，即 low[v] > dfn[u]，那麼我們斷言，從棧頂到 \(v\) 的所有節點（的點匯出子圖，下文忽略）形成了一個 E-BCC。將這些節點彈出。
考慮證明上述結論。不妨設割掉 \((u, v)\) 後形成的連通塊分別為 \(u\in U\) 和 \(v\in V\)。由於判定 \((u, v)\) 為割邊是在離開節點 \(v\) 回到節點 \(u\) 時進行的，所以當前棧中節點 \(v\) 往上一直到棧頂均屬於 \(V\)：越靠棧頂越晚被存取，而 \(V\) 中節點全都在 \(v\) 之後被存取，且 \(U\) 中節點一定在 \(v\) 之前被存取（時刻記住 \((u, v)\) 是割邊）。
對於 \(V\) 內部所有割邊，我們在 dfs 到它們時就已經處理掉了它們形成的 E-BCC。因此，\(V \cup S\) 的部分一定 不存在割邊，恰好為一個 E-BCC。反證法，若 \(V\cup S\) 的部分可以被分成兩個 E-BCC \(V_1\) 和 \(V_2\)，考慮 \(V_1\) 和 \(V_2\) 之間的唯一一條割邊 \((x \in V_1, y \in V_2)\)（如果割邊不唯一，那麼 \(V_1, V_2\) 就可以合併成一個 E-BCC 了啊）。首先由於 \(x, y\in T(v)\)，所以 \(x, y\) 這條割邊一定會在從 \(v\) 回溯到 \(u\) 之前被處理掉。不妨設 dfs 樹上 \(x\) 是 \(y\) 的祖先，我們在離開 \(y\) 回溯到 \(x\) 時，會將 \(x, y\) 判定為割邊，從而將 \(V_2\) 彈出 \(S\)，與 \(V_2 \subseteq S\) 矛盾。結論得證。
整個演演算法可以看成不斷從原圖上斷開一條 「偏僻」 的割邊，剝下一層連通分量的過程。「偏僻」 定性描述就是剝下的連通分量不存在割邊（已經斷開的割邊不算），那麼這個連通分量自然就是一個 E-BCC。對應到縮完點後形成的樹上，就是每次通過一條割邊剝下一個葉子節點（每個節點都是一個 E-BCC）。
上述思想在 V-BCC 縮點和 SCC 縮點時也會運用到，讀者需要仔細體會。
演演算法的時間複雜度是優秀的 \(\mathcal{O}(n + m)\)。程式碼見例題 III.
見 高階圖論 第三章圓方樹。
一道 tarjan 求割點的練手好題。
由於題目求的是有序對，因此不妨設封鎖節點 \(u\) 後形成的連通塊大小分別為 \(s_1, s_2, \cdots, s_k\)。不難求得答案為 \(\sum s_i(n - s_i)\)。
不要忘記 \(u\) 本身形成了一個大小為 \(1\) 的連通塊，以及除去所有判定 \(u\) 是割點的節點 \(v\) 形成的連通塊後還有一個大小為 \(s_k = n - 1 - \sum\limits_{i = 1} ^ {k - 1} s_i\) 的連通塊。
時間複雜度 \(\mathcal{O}(n)\)。程式碼。
雙倍經驗題。
題目相當於求新增最少的邊數使得整張圖變成一個 E-BCC，即不存在割邊。
考慮 E-BCC 縮點，得到的樹 \(T\) 上所有邊都是原圖上的割邊。根據求割邊的結論，如果我們在 \((u, v)\) 之間加一條邊，設 \(U\) 為 \(u\) 所在 E-BCC 在縮點後的樹上對應的節點，\(V\) 同理，那麼相當於將 \(U, V\) 之間簡單路徑上的所有邊在原圖上變成非割邊。
因此，我們希望用最少的路徑覆蓋 \(T\) 的每一條邊。對此有經典結論（或者直接感性理解），答案即 \(T\) 的葉子個數除以 \(2\) 上取整。
證明這是答案下界非常容易，因為每一條鏈至多消滅掉兩個葉子到它唯一相鄰的點的邊。當只有兩個節點的時候特殊討論一下，這是平凡的。接下來我們只需給出一個達到該下界的構造方法。
我們稱兩個節點匹配表示在最終方案中，存在一條連線它們的鏈。
首先，當葉子個數為奇數時，將一個葉子和度數 \(\geq 3\) 的節點匹配後可以轉化為葉子數量為偶數的情況。如果不存在度數 \(\geq 3\) 的節點，則 \(T\) 為一條鏈，與葉子個數為奇數矛盾。
考慮先將所有葉子任意兩兩配對，再調整。如果在當前方案中，存在一條邊 \((u, v)\) 沒有被覆蓋，考察斷掉 \((u, v)\) 後 \(u, v\) 分別所在的連通塊 \(U, V\)。
\(U\) 或 \(V\) 不可能只有一個葉子（這裡的葉子是相對於原樹而言的，即在原樹 \(T\) 上是葉子，而不是 \(U\) 本身的葉子），因為若非，則該唯一的葉子和另外某個葉子匹配時必然經過 \((u, v)\)，與 \((u, v)\) 沒有被覆蓋矛盾。
同理可以證明 \(U\) 或 \(V\) 不可能有奇數個葉子。
根據上述結論，當前方案必然是 \(U\) 的所有偶數個葉子兩兩匹配，\(V\) 的所有偶數個葉子兩兩匹配。
不妨設 \(U\) 某兩個配對的葉子為 \(u_1, u_2\)，它們在以 \(u\) 為根時的 LCA 為 \(u_d\)，對於 \(V\) 同理，定義 \(v_1, v_2\) 和 \(v_d\)。
當前的方案是 \(u_1\to u_d \to u_2\) 以及 \(v_1 \to v_d \to v_2\) 上的所有邊被覆蓋，但通過調整，令 \(u_1\) 和 \(v_1\)，\(u_2\) 和 \(v_2\) 匹配，則 \(u_i\to u_d \to u\to v \to v_d \to v_i\) 上的所有邊被覆蓋。原來被覆蓋的邊仍被覆蓋，同時 \((u, v)\) 也被覆蓋了。
因此，若對於當前方案，某條邊沒有覆蓋，通過上述調整一定能使得原來被覆蓋的邊仍被覆蓋，且該邊也被覆蓋，同時不改變原來 \(\dfrac {\# \mathrm{leaf}}{2}\) 的鏈的條數。答案上界得證。
時間複雜度 \(\mathcal{O}(n + m)\)。
#include <bits/stdc++.h>
using namespace std;
const int N = 5e3 + 5;
int n, m, dn, deg[N], dfn[N], low[N];
int cn, col[N], stc[N], top;
vector<pair<int, int>> e[N];
void form(int id) {
cn++;
for(int x = 0; x != id; ) col[x = stc[top--]] = cn;
}
void tarjan(int id, int eid) {
stc[++top] = id, dfn[id] = low[id] = ++dn;
for(auto _ : e[id]) {
if(_.second == eid) continue;
int it = _.first;
if(!dfn[it]) {
tarjan(it, _.second);
low[id] = min(low[id], low[it]);
if(low[it] > dfn[id]) form(it);
}
else low[id] = min(low[id], dfn[it]);
}
if(!eid) form(id);
}
int main() {
cin >> n >> m;
for(int i = 1; i <= m; i++) {
int u, v;
cin >> u >> v;
e[u].push_back(make_pair(v, i));
e[v].push_back(make_pair(u, i));
}
tarjan(1, 0);
if(cn == 1) puts("0"), exit(0); // 這句判斷其實不要也可以
for(int i = 1; i <= n; i++)
for(auto _ : e[i]) {
int it = _.first;
if(i < it && col[i] != col[it]) deg[col[i]]++, deg[col[it]]++;
}
int leaf = 0;
for(int i = 1; i <= cn; i++) leaf += deg[i] == 1;
cout << (leaf + 1 >> 1) << endl;
return cerr << "Time: " << clock() << endl, 0;
}
強連通分量全稱 Strong Connected Component，縮寫 SCC。以下是一些定義和基本性質：
強連通分量在求解與連通性有關的題目時很有用，因為在只關心連通性時，同一強連通分量內的所有點是等價的。
有了運用 tarjan 演演算法求解割點和割邊，V-BCC 和 E-BCC 縮點的先例，我們可以自然地將這些方法進行調整後用於求解強連通分量的縮點問題。
我們考察有向圖 dfs 樹 \(T_d\) 的形態，從而得到判定 SCC 的準則。
首先給出一個有關 \(T_d\) 的引理。如果 \(u\) 在 \(v\) 之前被存取且 \(u\) 可達 \(v\)，則 \(v\) 屬於 \(u\) 的子樹 \(T_d(u)\)。可以通過 dfs 的流程和 dfs 樹的定義輕鬆證明：在進入 \(u\) 之前，\(v\) 沒有被存取，但離開 \(u\) 的時候 \(v\) 已經存取過了。
除了樹邊以外，\(T_d\) 還有前向邊，返祖邊和橫叉邊。前向邊和返祖邊由無向圖 dfs 樹 \(T_u\) 的返祖邊的兩種定向方式得到，而橫叉邊是 \(T_d\) 某個節點的兩棵子樹之間的連邊。\(T_u\) 沒有橫叉邊，因為 \(T_u\) 的子樹具有獨立性，我們在用 tarjan 求割點的時候就已經強調過這一點。
當然，一個先存取到的 SCC 不可能向之後存取的 SCC 連橫叉邊 \(u\to v\)，因為若非，根據引理，\(T_d\) 上 \(u\) 是 \(v\) 的祖先，這樣 \(u\to v\) 就成了前向邊或樹邊，與 \(u\to v\) 是橫叉邊矛盾。筆者稱其為 橫叉邊的滯後性。
儘管子樹獨立性變弱了，但我們還是能夠發現一些性質，就是前向邊和橫叉邊不影響強連通性。下面證明這一點。
對於前向邊 \(u\to v\) 而言，\(u\) 本身就能通過樹邊到達 \(v\)，刪去後自然沒有任何影響。它甚至不影響連通性。
對於橫叉邊 \(u\to v\) 而言，\(u, v\) 一定在不同的 SCC。若非（即 \(u, v\) 強連通），類似 \(T_u\) 的子樹獨立性，考察 \(u, v\) 在 \(T_d\) 上的 LCA \(d\)。根據橫叉邊的滯後性，\(v\) 在 \(u\) 之前被存取。因為 \(u, v\) 強連通，所以 \(v\) 可達 \(u\)。結合這兩點，根據引理，\(T_d\) 上 \(v\) 是 \(u\) 的祖先，所以 \(u\to v\) 是返祖邊，與 \(u\to v\) 是橫叉邊矛盾。
對於返祖邊 \(u\to v\)，它會使 \(T_d\) 上 \(v\) 到 \(u\) 的路徑上所有點形成 SCC。多個返祖邊組合起來能夠形成更大更復雜的 SCC。
根據上述結論，有向圖 tarjan 演演算法的 low 陣列應當定義為子樹內所有節點的所有 返祖邊 能到達節點的最小時間戳。
容易證明每個 SCC 在 \(T_d\) 上只有一個最淺節點，我們希望在每個最淺節點處統計其對應的 SCC。考慮定性描述 「形成一個 SCC」 的情況。
對於節點 \(u\)，如果它不是某個 SCC 的最淺節點，由 SCC 的定義，它只經過返祖邊一定可以到達更淺的祖先。相反，如果它是，那麼它的整棵子樹都不能跳出 \(x\) 到達更淺的祖先。根據這一點，我們得到判斷 \(u\) 是某個 SCC 的最淺節點的充要條件：low[u] >= dfn[u]，也可以看做 dfn[u] == low[u]。
類似 E-BCC 縮點，我們時刻維護一個棧 \(S\)，表示已經存取過但還沒有確定形成 SCC 的節點。每次找到最淺節點 \(u\) 時，就將棧頂一直到 \(u\) 的所有節點彈出（由於 \(u\) 是該 SCC 第一個被存取到的節點，所以它在棧中位置最深），表示它們形成了一個 SCC。
演演算法的正確性依賴於彈出的所有節點的強連通性，以及對應 SCC 的極大性。證明方法和 E-BCC 縮點的正確性證明差不多，這裡簡要說明一下。
強連通性：設彈出的點集為 \(V\)，若 \(V\) 的點匯出子圖包含兩個 SCC \(G_1\) 和 \(G_2\)，設對應點集為 \(V_1\)，\(V_2\)，且 \(V_1\) 的最淺節點為 \(u\)，\(V_2\) 的最淺節點為 \(v\)，那麼在 dfs 的過程中回溯到 \(v\) 時，由於將 \(v\) 判定成 \(G_2\) 的最淺節點，同時 \(V_2\) 是在 \(V_1\) 之後存取的，所以不斷彈棧直到彈出 \(v\) 的過程中，彈出的點集 \(V'\) 一定包含 \(V_2\)。與 \(V_2 \subseteq V\) 矛盾。
極大性：如果存在 \(v\) 屬於 \(u\) 所在 SCC 但 \(v\notin V\)，根據 \(u\) 的最淺性，\(v\) 一定在此之前被彈出，所以 dfn[v] == low[v]，即 \(v\) 的子樹內不存在能到達 \(u\) 或其祖先的返祖邊，與 \(u, v\) 屬於同一 SCC 矛盾。
最後只剩下一個問題，就是如何求 low。對於樹邊 \(u\to v\) 而言，根據經驗自然是用 low[v] 更新 low[u]。主要是如何判斷邊的型別是橫叉邊，前向邊還是返祖邊。
對於前向邊 \(u\to v\) 而言，用 dfn[v] 更新 low[u] 沒有任何影響，因為 dfn[v] <= low[u]。
對於返祖邊 \(u\to v\) 而言，用 dfn[v] 更新 low[u]。
對於橫叉邊 \(u\to v\) 而言，不能用 dfn[u] 更新 low[v]，因為橫叉邊對強連通性沒有影響。我們已經證明過了 \(u, v\) 一定屬於不同 SCC。
考慮它們在 \(T_d\) 上的 LCA \(d\)，\(v\) 和 \(d\) 一定屬於不同 SCC，否則由於 \(d\) 可達 \(u\)，\(u\) 可達 \(v\)，而 \(v, d\) 強連通，即 \(v\) 可達 \(d\)，得出 \(u, v\) 強連通，矛盾。這說明從 \(v\) 回溯到 \(d\)，向 \(u\) 方向 dfs 時，\(v\) 所在 SCC 已經被彈出，即 \(v\) 不在棧中。
同時，由於返祖邊 \(u\to v\) 使得 \(u, v\) 在同一個 SCC 中，所以此時 \(v\) 一定沒有被彈出，即 \(v\) 在棧中。
綜合上述兩點，我們證明了以下做法的正確性：對於非樹邊 \(u\to v\)，若 \(v\) 不在棧中，則用 dfn[v] 更新 low[u]。
因為可以多次經過同一個點，所以一旦進入某個 SCC，就一定可以走遍其中所有點，獲得其中所有點權值之和的貢獻。但是離開後就沒法再回來了。
因此，將所有 SCC 縮點後得到 DAG，每個 SCC 縮點後的權值等於它所包含的所有點的權值之和，問題即找到最長的一條路徑使得路徑上所有 SCC 的權值之和最大。拓撲排序 DP 即可，時間複雜度 \(\mathcal{O}(n + m)\)。
由上我們可以發現 SCC 縮點經常和拓撲排序搭配在一起，因為縮點後的結果是一張有向無環圖。
E-BCC 和 V-BCC 縮點後均可以得到一棵樹，後者經過處理後就是圓方樹。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 5;
int n, m, cn, col[N];
int a[N], val[N], f[N], deg[N];
int top, stc[N], vis[N], dn, dfn[N], low[N];
vector<int> e[N], g[N];
void tarjan(int id) {
vis[id] = 1, dfn[id] = low[id] = ++dn, stc[++top] = id;
for(int it : e[id]) {
if(!dfn[it]) tarjan(it), low[id] = min(low[id], low[it]);
else if(vis[it]) low[id] = min(low[id], dfn[it]);
}
if(dfn[id] == low[id]) {
col[id] = ++cn;
while(stc[top] != id) col[stc[top]] = cn, vis[stc[top--]] = 0;
vis[id] = 0, top--;
}
}
int main() {
cin >> n >> m;
for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
for(int i = 1; i <= m; i++) {
int u, v;
scanf("%d%d", &u, &v);
e[u].push_back(v);
}
for(int i = 1; i <= n; i++) if(!dfn[i]) tarjan(i);
for(int i = 1; i <= n; i++) {
val[col[i]] += a[i];
for(int it : e[i])
if(col[i] != col[it]) {
g[col[i]].push_back(col[it]);
deg[col[it]]++;
}
}
queue<int> q;
for(int i = 1; i <= cn; i++) if(!deg[i]) q.push(i);
while(!q.empty()) {
int t = q.front();
q.pop(), f[t] += val[t];
for(int it : g[t]) {
f[it] = max(f[it], f[t]);
if(!--deg[it]) q.push(it);
}
}
int ans = 0;
for(int i = 1; i <= cn; i++) ans = max(ans, f[i]);
cout << ans << endl;
return 0;
}
強連通性相關首先考慮縮點建出 DAG。
對於連線 SCC \((S_1, S_2)\) 之間的邊，反向後使得 SCC 數量減少當且僅當 \(S_1\) 在 DAG 上能夠不經過該邊到達 \(S_2\)。可以 \(\mathcal{O}(nm)\) 求出任意兩點之間的路徑數對 \(2\) 取 \(\min\) 判斷。或者直接求路徑數取模，出錯的概率較小。
但是 SCC 內部的邊就不好辦了。如果反向 \(u\to v\)，我們斷言如果 \(u\) 還能到達 \(v\) 那麼連通性不變。
首先，對於所有 SCC 內部的點對 \((x, y)\)，從 \(x\) 到 \(y\) 要麼必經 \(u\to v\) 這條邊，要麼非必經。對於後者，反向 \(u\to v\) 不影響 \(x, y\) 的連通性。對於前者，若 \(u\) 仍能到達 \(v\) 則 \(x\) 仍能到達 \(y\)，否則反向邊 \(v\to u\) 不會產生任何影響。因為必經 \(u\to v\) 所以 \(x\) 沒有其它路徑到達 \(v\)，反向後 \(x, v\) 不連通自然引出 \(v\to u\) 無用。
綜上我們得到了判斷 SCC 內部邊 \(u\to v\) 反向後強連通性不變的充要條件：去掉 \(u\to v\) 後 \(u\) 仍能到達 \(v\)。這相當於對於一個點的每條出邊 \(u\to v_1, v_2, \cdots, v_i\)，我們都需求出 \(u\) 在不經過 \(u\to v_j\) 的情況下能到達哪些點。
考慮這是一個字首 \(v_1 \sim v_{j - 1}\) 和字尾 \(v_{j + 1} \sim v_i\) 的形式，因此正反各掃一遍，在掃每條出邊時記錄時刻每個點的可達性，並且在掃當前出邊 \(u\to v\) 時若 \(v\) 已經可達則將 \(u\to v\) 標記為去掉後仍可達。由於我們依次加入所有出邊時 SCC 內每個點只會被遍歷一次，故總時間複雜度為 \(\mathcal{O}(nm)\)。
dfs 到 \(u\) 時需及時返回，否則會遍歷到從 \(u\) 出發的不屬於當前字首或字尾的邊。更進一步地，發現對於連線 SCC 之間的邊 \(u\to v\)，我們也希望判斷去掉該邊後 \(u\) 能否到達 \(v\)。這和 SCC 內部的邊所需要求解的東西是一致的，因此可以將所有邊等價考慮。只不過對於不同 SCC 之間的邊，若 \(u\not\rightsquigarrow v\) 則反轉 \(u\to v\) 不會改變 SCC 個數，反之則改變。這和 SCC 內部的邊恰好相反。這樣我們就不需要顯式地建出 DAG 了。
對整張圖進行 \(\mathcal{O}(nm)\) 的深搜會 T 飛掉，我們需要更加高效的演演算法。考慮每次找到 \(u\) 的所有出邊中沒有被存取的第一個點，可以使用 bitset 的 _Find_first() 實現。
具體而言，設 vis 表示各個節點是否被存取，e[u] 表示 \(u\) 的所有出點，則 (~vis & e[u])._Find_first() 即為所求。時間複雜度 \(\mathcal{O}\left(\dfrac {n ^ 3}{w}\right)\)。
啟示：序列去掉一個位置的資訊可由字首和字尾合併得到。
程式碼。
首先，容易發現若一個大小大於 \(1\) 的 SCC 或自環（下稱為不合法結構）能夠到達教學樓，則該不合法結構內部每個點到教學樓的路徑數量都是無窮大。因此 SCC 縮點 + 建反圖 拓撲排序，不合法結構不能入隊。拓撲排序同時記錄路徑數 \(f_i\) 表示從 \(i\) 到 \(n+1\) 的路徑數量。因為不能取模，所以要對 \(36501\) 取 \(\min\)。
但題目沒有保證每個點都能到教學樓（題面有誤），所以需要先將反圖上入度為 \(0\) 的非教學樓點入隊跑一遍拓撲排序。注意此時不合法結構可以入隊，因為它們沒有到達教學樓的路徑。
最後，若出現沒有入隊的點，說明這個點能夠到達一個不合法結構，因此路徑數同樣為無窮大。此外，若 \(f_i>36500\) 也不符合題意。時間複雜度線性。
vector 存圖會 MLE，原題空間限制 64MB。程式碼。
對於一個 SCC ，將其縮成一個點不影響答案。而題目給定的性質說明圖的連通性可以用一棵樹刻畫，具體來說，拓撲排序，保留每個點最後一條入邊。得到一棵外向樹。
對於給定的 \(2(k + 1)\) 個城市端點，若 \(i\) 是 \(j\) 的祖先，且 \(s\) 能到達 \(i\)，\(j\) 能到達 \(t\)，說明 \(i\to j\) 這條鏈上所有城市都有可能經過，樹剖求鏈並即可。
時間複雜度 \(\mathcal{O}(n\log n\log\log n)\)。\(\log \log n\) 是排序的複雜度。
程式碼。
尤拉，永遠滴神！
做題時基本用不到上述定義（大霧）。
不嚴謹地說，尤拉圖能夠從任意一點作為起點一筆畫完整張圖然後回到該點，而半尤拉圖只能從某兩個點 \(S,T\) 開始才能畫完整張圖，其中 \(S,T\) 分別作為起點和終點。
尤拉圖的判定：一張無向圖 \(G\) 是尤拉圖，當且僅當 \(G\) 是連通圖且每個頂點的 度數都是偶數。一張有向圖 \(G\) 是尤拉圖，當且僅當 \(G\) 是 SCC 且每個頂點的入度和出度相等。
考慮證明上述結論。
無論是對於無向圖還是有向圖而言，必要性都是顯然的。考慮最終歐拉回路的形態，每次進入一個點，都要從該點走出去，所以出邊和入邊必須兩兩抵消。對於起始點，它一開始走出去的邊和最後走回它的邊同樣抵消了，所以有向圖存在歐拉回路必須滿足每個點出度和入度相等。同理可證無向圖每個點的度數必須為偶數。
充分性通過構造法證明。考慮無向圖，首先找到圖上任何一個迴路 \(P\)（不需要是歐拉回路）。因為除掉所有孤立點，每個點的度數都 \(\geq 2\)，所以迴路必然存在。然後從圖上刪去 \(P\) 的所有邊，並刪去所有孤立點。形成的所有子圖仍然滿足每個點的度數均為偶數，因為 \(P\) 中每個點的度數為 \(2\)。由於每個子圖均與 \(P\) 有交點，所以只需要將子圖的歐拉回路接到 \(P\) 上即可得到原圖的歐拉回路。因此我們對子圖進行同樣的操作。邊的個數有窮，所以整個過程必然結束，繼而我們得到原圖的歐拉回路。同理可證有向圖歐拉回路判定條件的充分性。
半尤拉圖的判定：一張無向圖 \(G\) 是半尤拉圖，當且僅當 \(G\) 存在兩個奇度數頂點。一張有向圖 \(G\) 是半尤拉圖，當且僅當 \(G\) 弱連通，恰存在一個頂點使得出度減入度等於 \(1\)，恰存在一個頂點使得入度減出度等於 \(1\)，且剩餘所有頂點出入度相等。弱連通定義為將所有有向邊替換為無向邊後，整張圖連通。
Hierholzer 演演算法的核心是不斷往當前迴路的某個點中插入環，這和歐拉回路存在的判定條件的充分性證明如出一轍，或者說完全等價。
先考慮有向圖吧，因為有向圖不需要考慮重邊的問題。
根據流程，我們有一個樸素的實現方法：首先 dfs 找到經過某個點的任意一個環 \(P\)（不需要是簡單環），將 \(P\) 上的所有點標記為已刪去。然後依次加入 \(P\) 上的每個節點 \(p_1, p_2, \cdots, p_{|P|}, p_1\)。加入 \(p_i\) 之前，我們先遞迴找到 \(p_i\) 所在子圖（我們刪去了一些邊）的歐拉回路，然後插入當前路徑。因此這是一個遞迴形式的演演算法。
每次列舉到一個點時，我們都要遍歷它的所有出邊以找到第一個沒有被刪去的邊，複雜度為 \(\mathcal{O}(m ^ 2)\)。
若用雙向連結串列維護每個點剩餘的所有出邊，則每條邊只會被遍歷一次，時間複雜度 \(\mathcal{O}(n + m)\)。
進一步地，我們發現每次刪去的環邊一定是每個節點所有沒有被刪去的出邊中開頭的若干個。也就是說，如果給 \(u\) 的所有出邊 \((u, v_i)\) 欽定一個遍歷順序 \((u, v_1), \cdots, (u, v_{out(u)})\)，那麼找環時被刪去的一定是開頭的若干條邊 \((u, v_1), (u, v_2), \cdots, (u, v_k)\)。因為我們不會因找不到環而反悔掉走某一條邊的操作。
不斷無腦深搜，最終一定能找到環。
證明該結論。不妨設我們從 \(u\) 開始找環，每次走當前節點第一條沒有被刪去的出邊並刪去。走到節點 \(v \neq u\) 時，設這是我們第 \(i\) 次進入 \(v\)，那麼我們只會離開 \(v\) 共 \(i - 1\) 次（每次離開必然對應一次進入，而在第 \(i\) 次進入之前，只有 \(i - 1\) 次進入）。故此時我們只刪掉了 \(v\) 的 \(i - 1\) 條出邊，而 \(v\) 有不少於 \(i\) 條出邊：第 \(i\) 次進入 \(v\) 意味著 \(in(v) \geq i\)，而 \(in(v) = out(v)\) 所以 \(out(v) \geq i\)。因此我們必然能從 \(v\) 走出去到別的節點。
因此，最終必然只可能在 \(u\) 處走不到其它節點。但這意味著我們已經找到了一個環。
根據上述結論，我們不需要維護雙向連結串列了。存圖用的鏈式前向星可以滿足我們的要求，因為我們每次只會刪去開頭的出邊。這樣改進後，連結串列頭就和網路最大流 Dinic 演演算法的當前弧非常相似，都是 記錄第一個有用的邊 以省去一條條跳無用邊的時間。
該結論同時也證明了找到一個環的複雜度關於環上邊數線性，所以總複雜度即 \(\mathcal{O}(n + m)\)。
注意，需要使用雙向連結串列維護將一個環插入當前迴路的過程，否則複雜度會退化成 \(\mathcal{O}(n(n +m))\)（如果一旦走到目標節點而非目標節點不可以在往外走時就認為找到環，複雜度會退化成 \(\mathcal{O}(m(n + m))\)）。因為這樣處理一個環的複雜度變成了所有未處理的邊的個數之和。
上述做法的時間複雜度已經足夠優秀，但實現起來稍微有些複雜。我們希望演演算法能夠更簡單。
我們可以用自己的語言描述複雜的方法幹了些什麼，再思考有哪些地方可以簡化。
從整體上考察，我們無非就是實現了這樣的步驟：從一個起點開始找到一個環，然後以環上的每個起點開始找到一個環 …… 不斷遞迴下去。
然後思考究竟是哪裡麻煩了。我們會發現，為了依次從環上的每個起點開始找環，我們需要先 顯式 地將這個環找到，排出來，再依次處理上面的所有節點。所以我們需要一個 dfs 函數找環，另一個遞迴式函數解決歐拉回路問題。
這樣太蠢了，因為無論以怎樣的順序安排環上節點的找環順序，都不會影響歐拉回路的正確性。我們只是找環並插入啊，換個順序又不會讓問題變得無解。
因此，我們直接在 dfs 找環的回溯過程中，直接對環上的每個節點找環。換句話說，我們將原來找環的順序倒過來，這樣我們就沒有必要先顯式地找到當前環了，而是在回溯的過程中，一邊對當前點找環，一邊往回路中插入當前環。
綜上，我們得到了求解歐拉回路的最常用演演算法 —— Hierholzer 演演算法的具體步驟：遍歷當前節點 \(u\) 的所有出邊 \((u,v)\)，若 \((u,v)\) 未走過，那麼向節點 \(v\) 深搜。遍歷完所有出邊後，將 \(u\) 加入路徑。最終得到的就是一條反著的尤拉路徑。倒過來即可。
如果要求字典序最小，只需在一開始對每個點的所有出邊從小到大排序。這樣一來，歐拉回路上從左往右看，每個點的後繼都取到了理論最小值。
以上，我們通過兩小節的篇幅提出並優化了有向圖歐拉回路的求解方法。
對於無向圖的歐拉回路，我們可以類似有向圖歐拉回路一樣做，唯一的注意點是我們需要對邊判重。使用求橋邊時的成對變換技巧，用 \(2k\) 和 \(2k + 1\) 儲存一條邊的兩個方向，並開桶記錄。不能只判返祖邊，因為可能有重邊。
對於無向圖和有向圖的尤拉通路，注意必須從奇點或唯一的出度大於入度的點開始 dfs。其它地方和歐拉回路沒有區別。
模板題 P7771 【模板】尤拉路徑 程式碼如下。
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int n, m, lar, top, stc[N], in[N], hd[N];
vector<int> e[N];
void dfs(int id) {
for(int &i = hd[id]; i < e[id].size(); ) dfs(e[id][i++]);
stc[++top] = id;
}
int main() {
cin >> n >> m;
for(int i = 1; i <= m; i++) {
int u, v;
scanf("%d%d", &u, &v);
e[u].push_back(v), in[v]++;
}
for(int i = 1; i <= n; i++) {
sort(e[i].begin(), e[i].end());
if(abs((int) e[i].size() - in[i]) > 1) puts("No"), exit(0);
if(e[i].size() > in[i])
if(lar) puts("No"), exit(0);
else lar = i;
}
dfs(lar ? lar : 1);
if(top != m + 1) puts("No");
else {
reverse(stc + 1, stc + top + 1);
for(int i = 1; i <= top; i++) cout << stc[i] << " ";
}
return 0;
}
無向圖最小字典序尤拉路徑板題。注意有重邊，所以只能記錄邊的編號而非兩個頂點以判重。
從每個字串第一個字元向最後一個字元連邊，跑有向圖歐拉回路即可。注意對鄰接連結串列排序要按照每條邊儲存的字串的字典序排序，而非指向節點的編號大小。
板題。
每條路徑片段的限制形如在片段中出現的相鄰兩條邊必須先後走，因為一條邊有向邊僅出現一次。
所有限制形成一條邊先後走的關係的鏈，類似 CSP2019 T4 樹上的數，將這條鏈縮成從起點到終點的一條邊，跑歐拉回路。最後輸出這條邊時要再展開成鏈，因此要記錄每條鏈上的節點順序。
若限制關係出現環或分叉則無解，這可以通過並查集或連結串列維護。時間複雜度線性對數。
細節還是挺多的，程式碼。
設 \(f(i)\) 表示以 \(i\) 為一端的需要經過的邊的數量。對於一條迴路，所有點度數均為偶數，因此一次操作後 \(f(i)\) 的奇偶性不變。故若存在 \(i\) 使得 \(f(i)\) 是奇數，則無解。否則，注意到有解是需要經過的邊形成的圖的每個連通塊均存在歐拉回路的充要條件，對這張圖跑一遍歐拉回路。由於要求不能經過相同的點，而路徑上相同的點之間也一定是迴路，所以藉助棧把相同的點之間的迴路彈出。時間複雜度 \(\mathcal{O}(n + m)\)。
對於不需要經過的邊，可以直接忽略，這是因為是否有解與這些邊無關：如果 \(f\) 均為偶數，我們必然能構造出一種不經過需要修改的邊，反之無解。