作者：SovietPower✨
連結：https://ac.nowcoder.com/discuss/186584
來源：牛客網
度數序列
對于無向圖，
為每個點的度數。有
（每條邊被計算兩次）。有偶數個度數為奇數的點。
Havel–Hakimi算法
給定一個由有限多個非負整數組成的度數序列，是否存在一個簡單圖使得其度數序列恰為這個序列。
令
為有限多個非負整數組成的非遞增序列。
可簡單圖化當且僅當有窮序列
隻含有非負整數且是可簡單圖化的。
序列
可簡單圖化是指存在一個無向圖（無重邊無自環），使得其度數序列恰為
。
（這個其實就是很顯然的東西。。主要是一個定義）
Erdős–Gallai定理
令
為有限多個非負整數組成的非遞增序列。
可簡單圖化當且僅當這些數字的和為偶數，且
，對于任意
都成立。
也不難了解。對前
個點配置設定度數，除了兩兩能連
條邊外，剩下的度數由後面點的度數補。
因為
非遞增，從小到大枚舉
，維護
字尾與
取
的和（
都是單調的，維護從哪開始
的結果是
）。就可以
判斷了。
例題：Good Bye 2018 E，NEERC2013 K.Kids in a Friendly Class。
歐拉路與歐拉回路
給定一張無向/有向圖，求一條經過所有邊恰好一次的回路。有解當且僅當所有點 度數為偶數(無向)/入度等于出度(有向)。任選一點開始dfs，每條邊隻經過一次。回溯時将回溯的邊加入隊列，最後隊列的逆序就是答案。時間複雜度
。
歐拉路徑也可以用一樣的方法求出（找度數為奇數的點進行DFS）。
歐拉回路：
- 有向圖：所有點的出度入度都相等；從任意一點都可實作。
- 無向圖：所有點度數都為偶數。
：
- 有向圖：有兩個點可以入度出度不相等（差不大于一），即起點終點；起點入度小于出度，終點入度大于出度 。
- 無向圖：僅有兩個點度數為奇數。
注：必須為連通圖（用并查集判斷）。兩筆畫問題
：
有解當且僅當入度為奇數的點不超過四個。将其中兩個點加一條邊後求歐拉路徑，然後在這條邊處斷開成兩條歐拉路即可。時間複雜度
。
題目：UOJ#117(模闆)、題集。
Prufer序列
這裡很全，可以看這兒。
Defination：
Prufer序列是一種無根樹的編碼表示。
對于一棵
個點的無根樹，對應唯一一串長度為
的
序列。
無根樹轉
序列
定義無根樹中度數為
的節點是葉子節點，每次找到編号最小的葉節點删除，在序列中添加與之相鄰的點。如此重複直到剩下最後兩個節點。
上圖對應無根樹的
序列為
。
序列轉有根樹
給定點集
，
序列
。
每次取出
序列中的第一個元素
，在
中找在目前
序列中沒有出現的第一個元素
，在
和
間連一條邊；将
從
序列中删除，
從
中删除。最後
中還剩下
個元素，在這
個元素間連一條邊。
生成樹計數
Cayley定理：完全圖的生成樹個數為
。如果每個點的度數為
，那麼生成樹個數為
。每個連通塊大小為
，那麼添加一些邊将這些連通塊連通的生成樹個數為
。
題目：題集。
Matrix-Tree定理
無向圖生成樹計數：令
（基爾霍夫矩陣=度數矩陣-邊矩陣），然後去除
的任意一行一列得到
，
的行列式即生成樹個數。
有向圖生成樹計數：與無向圖不同的是，
矩陣為入度/出度矩陣分别對應外向樹/内向樹。且删掉第
行第
清單示以
為根節點的生成樹個數。
題目：題集。
最小生成樹 Borůvka算法
一開始每個連通分量是一個點本身。
每輪枚舉所有屬于不同連通分量的邊，每個連通分量選擇和其他連通分量相連的最小的邊，然後合并。
每輪連通塊個數至少減半，是以最多進行
輪。時間複雜度
。
具體實作直接用并查集即可。代碼可以看這裡。
題目一般用來做邊權與點權相關，還是個完全圖，求MST的題？
1. 有
個點的完全圖，每個點的權值為
，兩個點之間的邊權為
。求這張圖的最小生成樹。
2.CF888G。有一張
個點的完全圖，每個點的權值為
，兩個點之間的邊權為
。求該圖的最小生成樹。
。
最小瓶頸生成樹
使得生成樹樹上最大邊權值最小。
方法1：最小生成樹一定是最小瓶頸生成樹。
方法2：二分答案，看點是否連通。
方法3：類比找第k大值的方法(`nth_element`)，首先随機一個邊權$w$。然後将不超過這個邊權的邊加入，周遊這張圖。
如果圖連通，那麼瓶頸不超過$w$，于是隻需考慮邊權不超過$w$的邊；否則将這些連通點縮起來，考慮邊權大于$w$的邊。
每次将問題的規模縮小至一半。期望時間複雜度$T(m)=T(frac m2)+O(m)=O(m)$。
單源最短路(SSSP)
（貪心）或者
（動态規劃）。
時間複雜度
或者
。
一些變種
邊權是
：雙端隊列，如果是
在頭部插入，否則在尾部插入。
最長路徑不超過
, 正權圖：使用
的桶+連結清單維護這些點（代替堆），時間複雜度
。
關于判負環
複雜度
。代碼實作可以記錄最短路樹上的深度來判環，而不是入隊次數，這樣會有優化。
if
差分限制
大體過程：（具體可以看這裡）
考慮最短路中的松弛操作：
，也就是強制使得
滿足
。
是以對于
的限制，可以連一條邊
。這樣求
的最大值，就是求
的最短路。
如果限制是
，同理連邊
。
的最小值就是求
的最長路。
如果兩種限制都有，就把
變成
。
解的存在性：
比如求
的最大值：若圖中存在負環，則
的最短路無窮小，則不存在最大值（無解）。若
和
就不在同一連通塊，則
的最短路無窮大，最大值無窮大（或者存在無數多解）。
否則有解。
PS：
可以根據入隊次數判負環，也可以據此判正環。雖然效率都不高就是了。
不能求最長路（本質是貪心）。
如何判斷解唯一：
對原圖求一遍最短路。将原圖取反，邊權取反，求一遍最長路。
一個标号對應的是能取到的最小值，一個是最大值。
如果相同則解唯一。（沒什麼用）
題目：題集。
多源最短路(APSP)
算法（可用于負權圖）：
算法
原理：首先給圖中每個點一個權值
，把每條邊的邊權
改成
。
對于$
的一條路徑
，權值為
是以這麼做不會改變最短路。（具體也可以看這裡）
實作：第一次SPFA預處理$1$到每個點的距離
，記
。然後把邊權
改為
。
其中$
為給每個點設定的權值，
。
由不等式可以得到
，也就是改完之後所有邊權非負。
之後可以每個點用
跑。就是
啦。
這樣也可以實作
跑費用流。
半徑 直徑 (正權圖)
（後面可能就直接抄dls課件了QAQ）
的偏心距
直徑
半徑
中心
（要求定義在點上）
絕對中心（可以定義在邊上）
絕對中心
相關：求最小直徑生成樹（差不多）。
實作：固定一條
，考慮上面的點
的偏心距。
假設第三個點是
，
。
那麼對應的折線為
。
那麼偏心距為
條折線的最大值形成的折線。
按左端點排序維護一下。時間複雜度
最小直徑生成樹
即絕對中心的最短路樹。
如何證明？
注意一棵樹
的直徑為半徑的兩倍(對絕對中心來說)。如果最小直徑生成樹$T’$不包含絕對中心，那麼取
的絕對中心
，顯然沖突。
拓撲排序
每次去掉圖中入度為$0$的點。
時間複雜度
。
如果最後不為空集，那麼這個圖不為DAG。（否則每個點入度不為0，即每個點可以選擇一個前趨，沿着前趨走根據抽屜原理一定能找到相同點，也就是一個環。）
按照反圖DFS，出棧序列就是一個合法的拓撲序列。
scc縮點順序也是一個合法拓撲序。
求字典序最小的拓撲序
每個點有不同的标号，要使得拓撲序最小。
将拓撲排序的隊列改成優先隊列即可。
最小拓撲序的一個變種
使得最後的拓撲序中1的位置盡量靠前，如果相同比較2的位置，依次類推。
首先考慮如何求1最早出現的位置，可以将原圖反向，然後每次彈除了1之外的元素，直到隊列隻剩下1為止。
這是反圖中1的最晚的出現的位置，也就是原圖中最早的。
根據是否在隊列裡，這個圖被分成兩部分，在對應的圖中用同樣的方法處理2，依次類推。
容易發現每次找盡量大的元素出隊，能完成上述的過程。
是以等價于反圖最大字典序。
題目：題集。
二分圖比對
Hall's marriage theorem（霍爾定理）
對于一個二分圖
，記
為
的一個子集，
為所有
中所有點的相鄰點的并集。
一個圖有完備比對當且僅當
的所有子集
都有
。
對一般圖的推廣：
：每個正則二分圖都有完備比對。
Kőnig's theorem
最小點覆寫=最大比對 (與最大流最小割定理等價)
最大獨立集=點數-最大比對 (獨立集為點覆寫的補集)
最小邊覆寫=最大獨立集 (獨立集中每個點需要一條邊去覆寫)
DAG最小路徑覆寫
覆寫所有的邊：每條邊下界設為1, 然後求最小流。
覆寫所有的點：建立二分圖，對于
的邊，看做二分圖中的
，然後答案為點數-最大比對。
定理: 最大反鍊=最小鍊覆寫；最短的最長鍊=最小反鍊劃分數-1（？存疑。見BZOJ4160）。（當然這個不應該隻放在二分圖部分的）
題目：題集。
連通分量
強連通分量
。
将一個圖的所有強聯通分量縮起來會得到一個DAG。
雙聯通分量
點連通度: 最小的點集使得删去之後圖不連通
邊連通度: 最小的邊集使得删去之後圖不連通
如果一個圖的點連通度大于1，那麼是點雙連通的，邊連通同理。
雙聯通分量為圖中的極大雙聯通子圖。
割點和橋
考慮DFS樹，每條非樹邊對應着一個點到祖先的路徑。對于一條非樹邊隻要把對應的邊打上标記即可。
比如對于$(u,v)$這條非樹邊，隻要在$u$點打上$+1$的标記，$v$點打上$-1$的标記。
$x$到$fa[x]$的樹邊的覆寫次數為子樹内所有标記的和。
割點同理（注意特判根節點和葉節點）。
（emm沒看懂下面要幹嘛）
：題集。
2-SAT
一堆變量的二進制限制，問是否存在合法的指派。
：例題，題集。
曼哈頓距離與切比雪夫距離
将原坐标系每個點的坐标
變為
，則原坐标系中的曼哈頓距離等于新坐标系中的切比雪夫距離。
反過來，将原坐标系每個點的坐标
變為
，則原坐标系中的切比雪夫距離等于新坐标系中的曼哈頓距離。
例題：BZOJ3170 松鼠聚會。
與作者交流：https://ac.nowcoder.com/discuss/186584
更多算法和題解：https://ac.nowcoder.com/acm/contest/discuss