圖論
圖論
圖論是數學的一個分支。它以圖為研究對象。圖論中的圖是由若干給定的點及連接兩點的線所構成的圖形，這種圖形通常用來描述某些事物之間的某種特定關係，用點代表事物，用連接兩點的線表示相應兩個事物間具有這種關係。
歐拉迴路
前置知識
dfs（深度優先搜索）
深度優先搜索是一種在開發爬蟲早期使用較多的方法。它的目的是要達到被搜索結構的葉結點(即那些不包含任何超鏈的HTML文件) 。在一個HTML文件中，當一個超鏈被選擇後，被鏈接的HTML文件將執行深度優先搜索，即在搜索其餘的超鏈結果之前必須先完整地搜索單獨的一條鏈。深度優先搜索沿著HTML文件上的超鏈走到不能再深入為止，然後返回到某一個HTML文件，再繼續選擇該HTML文件中的其他超鏈。當不再有其他超鏈可選擇時，說明搜索已經結束。
邊權
離散數學或數據結構中，圖的每條邊上帶的一個數值，它代表的含義可以是長度等等，這個值就是邊權
歐拉路徑
如果圖中的一個路徑包括每個邊恰好一次，則該路徑稱為歐拉路徑。
歐拉迴路
首尾相接的歐拉路徑稱為歐拉迴路。
判定
由於每一條邊都要經過恰好一次，因此對於除了起點和終點之外的任意一個節點，只要進來，一定要出去。
一個無向圖存在歐拉迴路，當且僅當該圖所有頂點度數都為偶數，且該圖只有一個存在邊的連通塊。
一個無向圖存在歐拉路徑，當且僅當該圖中奇點的數量為0或2，且該圖只有一個存在邊的連通塊。
一個有向圖存在歐拉迴路，當且僅當所有點的入度等於出度。
一個混合圖存在歐拉迴路，當且僅當存在一個對所有無向邊定向的方案，使得所有點的入度等於出度。需要用網路流。
求法
我們用 dfs來求出一張圖的歐拉迴路。
我們給每一條邊一個 vis數組代表是否訪問過，接下來從一個點出發，遍歷所有的邊。
直接dfs並且記錄的話會有一些問題。
為了解決這個問題，我們在記錄答案的時候倒著記錄，也就是當我們通過 (u, v) 這條邊到達 v 的時候，先把 v dfs 完再加入 (v, u) 這條邊。
還有一點需要注意。因為一個點可能被訪問多次，一不小心可能會寫成 O(n 2 ) 的（因為每次遍歷所有的出邊）。解決方案就是設一個cur數組，每次直接從上一次訪問到的出邊繼續遍歷。
時間複雜度 O(n + m)。
程式碼
void dfs(int x)
{
for(int&hd=head[x];hd;hd=e[hd].nxt)
{
if(flag[hd>>1])continue;
flag[hd>>1]=1;
dfs(e[hd].to);
a[++top]=x;
}
}拓撲排序
定義
所謂拓撲排序，就是把有向圖上的 n 個點重新標號為 1 到 n，滿足對於任意一條邊 (u, v)，都有 u < v。
並不是所有的圖都能進行拓撲排序，只要圖中有環，那麼就可以導出矛盾。
可以進行拓撲排序的圖稱為有向無環圖（DAG），有很多優美的性質，比如可以在拓撲序上進行 DP（動態規劃）。
我們記錄一下每一個點的入度和出度，用一個隊列維護當前所有入度為 0 的點。 每次拿出來一個入度為 0 的點並且將它加到拓撲序中，然後枚舉出邊更新度數。 時間複雜度O(n + m)。
（在拓撲排序的過程中可以順帶進行 DP）
程式碼
for(int i=1;i<=n;i++)
if(d[i]==0)q.push(i);
while(!q.empty())
{
int node=q.front();
q.pop();
res[++top]=node;
for(int hd=head[node];hd;hd=e[hd].nxt)
{
d[e[hd].to]--;
if(d[e[hd].to]==0)
q.push(e[hd].to);
}
}最短路
所謂最短路，就是把邊權看做邊的長度，從某個點 S到另一個點 T 的最短路徑。
用更加數學化的語言描述就是，對於映射 f : V → R，滿足 f(S) = 0 且 ∀(x, y, l) ∈ E, |f(x) − f(y)| ≤ l 的情況下，f(T) 的最大值。
單源最短路——Dijkstra
在所有的邊權均為正的情況下，我們可以使用 Dijkstra 算 法求出一個點到所有其它點的最短路徑。
我們維護一個集合，表示這個集合內的點最短路徑已經確定了。
每次我們從剩下的點中選擇當前距離最小的點 u 加入這個集合，然後枚舉另一個點 v 進行更新：
dv = min(dv, du + w(u, v))
直接這樣做時間複雜度是 O(n 2 ) 的。
優化
我們注意到，複雜度主要來源於兩個地方。
第一個是找出當前距離最小的點。這個可以用堆很容易地實現。
第二個是枚舉 v，如果我們用鄰接表存圖，可以降到邊數級別。
這樣我們就把複雜度降到了 O((n + m) log n)。
單源最短路——Bellman-Ford
另一種求單源最短路的演算法，複雜度不如Dijkstra優秀。
考慮在上面出現過的鬆弛操作：
dv = min(dv, du + w(u, v))
由於最短路徑只會經過最多 n 個點，因此每一個點的最短 路徑只會被鬆弛至多 n − 1 次。
所以我們可以對整張圖進行 n − 1 次鬆弛操作，每次枚舉所有的邊進行更新。
時間複雜度 O(nm)。
SPFA
它死了。（不要用，它的複雜度是錯誤的）
應用：費用流
Bellman-Ford 演算法不夠優秀，於是我們嘗試改進這個演算法。
注意到，在進行鬆弛操作的時候，如果點 u 的距離一直沒有發生變化，那麼就不需要再枚舉這個點的出邊進行鬆弛了。
也就是說我們可以用一個隊列保存所有距離發生變化的點， 每次取出一個點進行更新。
於是 SPFA就誕生了。
如果圖是隨機的，SPFA的期望時間複雜度約為 O(2m)，比 之前提到的任何一個演算法都優秀，而且還可以有負權。
但是在最壞情況下它的複雜度和 Bellman-Ford 相同，都是 O(nm)，在正式比賽中，沒有哪個出題人會放過它。（因為其複雜度本來就是錯的）
多源最短路——Floyd
對於一張圖，我們希望求出任意兩個點之間的最短路徑。
我們用 DP（動態規劃） 的思想。設 fi,j,k 表示從 i 到 j，途中僅經過前 k個點的最短路。
由於每一個點在最短路中只會出現一次（不然就出現負環了，不存在最短路），所以可以很寫出轉移方程：
fi,j,k = min(fi,j,k−1, fi,k,k−1 + fk,j,k−1)
時間複雜度是 O(n 3 )。
在實際求的過程中，最後一維可以用滾動數組優化掉，所以空間複雜度是O(n 2 )。
程式碼
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
注意三層循環的順序不能顛倒。
Floyd 傳遞閉包
有時候，我們需要維護一些有傳遞性的關係，比如相等，連通等等。（12連通，23連通，則 13連通）
初始條件往往是已知若干個點對具有這些關係，然後讓你弄 出來所有的關係。
可以直接把 Floyd 演算法做一下調整——
dis[i][j]=dis[i][j]|(dis[i][k]&dis[k][j]);
這個演算法叫做傳遞閉包。
多源最短路——Johnson 重賦權
對於多源最短路，如果我們枚舉一個點然後跑堆優化的 Dijkstra，那麼複雜度是 O(nm log n) 的，在圖比較稀疏的情況下，這個複雜度要優於 Floyd 演算法的 O(n 3 )。
但是 Dijkstra 演算法要求所有邊權均非負。
於是就有了重賦權的技巧。
我們新建一個 0 號點，並且從這個點出發向所有點連一條邊 權為 0 的邊，然後跑單源最短路。（SPFA 或者 Bellman-Ford）
設距離數組為 h，接下來對於每條邊 (u, v)，令 w ′ (u, v) = w(u, v) + h(u) − h(v)。
這樣所有的邊權就都變成非負了，我們就可以跑 Dijkstra 演算法了。
證明
首先由於 h(v) ≤ h(u) + w(u, v)，新圖的邊權一定非負。
設新圖上的最短路徑為 d ′，原圖上的最短路徑為 d。
d ′ (u, v) = min a1,a2,…,ak w ′ (u, a1) + w ′ (a1, a2) + · · · + w ′ (ak, v)
= min a1,a2,…,ak w(u, a1) + (h(u) − h(a1)) + w(a1, a2)+ (h(a2) − h(a1)) + · · · + w(ak, v) + (h(v) − h(ak))
= h(u) − h(v) + min a1,a2,…,ak w(u, a1) + · · · + w(ak, v)
= h(u) − h(v) + d(u, v)
最短路樹（最短路圖）
所謂最短路樹，就是在求完從 S 出發的單源最短路之後，
只保留最短路上的邊形成的數據結構。
只需要在求的過程中維護一個pre數組表示這個點的前驅即可。很多最短路的變種都需要用這個演算法。
最小生成樹
Prim 演算法
類比 Dijkstra 演算法，我們維護一個集合 S，表示這個集合中 的生成樹已經確定了。
演算法流程和Dijkstra一樣，唯一的區別是用w(u, v) 去更新 dv 而不是用 du + w(u, v)。
時間複雜度 O(n 2 )，同樣可以用堆優化。
Kruskal 演算法
前置知識
並查集演算法
並查集主要用於解決一些元素分組的問題。它管理一系列不相交的集合，並支援兩種操作：
合併：把兩個不相交的集合合併為一個集合。
查詢：查詢兩個元素是否在同一個集合中。
優化
路徑壓縮（O(logn)）+安值合併（O(logn)）→O(αn)（αn在108數據內不超過4，可視為常數）
程式碼
find(int x)
{
return x==pa[x]?x:pa[x]=find(pa[x])
}因為是求的最小生成樹，所以我們用貪心的思路，把所有的邊權從小到大排序，然後一條一條嘗試加入，用並查集維護連通性。
可以發現這樣一定能得到原圖的最小生成樹。
證明
如果某一條邊 (u, v) 不屬於最小生成樹，那麼考慮最小生成樹上 連接 u, v 的路徑，這上面一定有一條邊權不小於 w(u, v) 的邊 （因為我們是從小到大枚舉的所有邊），這樣替換後答案一定不會變劣。
時間複雜度 O(m log m)。
Kruskal 重構樹
前置知識
dfs（深度優先搜索）
LCA（最近公共祖先）
在一棵沒有環的樹上，每個節點肯定有其父親節點和祖先節點，而最近公共祖先，就是兩個節點在這棵樹上深度最大的公共的祖先節點。
LCA主要是用來處理當兩個點僅有唯一一條確定的最短路徑時的路徑。
樹上倍增
用於求LCA（最近公共祖先）。
倍增的思想是二進位。
首先開一個n×logn的數組，比如fa[n][logn],其中fa[i][j]表示i節點的第2^j個父親是誰。
然後，我們會發現一個性質：
fa[i][j]=fa[fa[i][j-1]][j-1]
用文字敘述為：i的第2^j個父親 是i的第2^(j-1)個父親的第2^(j-1)個父親。
這樣，本來我們求i的第k個父親的複雜度是O(k)，現在複雜度變成了O(logk)。
Kruskal 重構樹是基於 Kruskal 最小生成樹演算法的一種算 法，它主要通過將邊權轉化為點權來實現。
流程
將所有邊按照邊權排序，設 r(x) 表示 x 所在連通塊的根節點。（注意這裡要用並查集）
枚舉所有的邊 (u, v)，若 u, v 不連通，則新建一個點 x，令 x 的權值為 w(u, v)。 連接 (x, r(u)) 和 (x, r(v))。 令 r(u) = r(v) = x。
不斷重複以上過程，直到所有點均連通。
時間複雜度 O(m log m)。
性質
這樣，我們就得到了一棵有 2n − 1 個節點的二叉樹，其中葉節點為原圖中的點，其餘的點代表原圖中的邊，並且滿足父節點權值大於等於子節點。
它有什麼用呢？
求 u, v 之間路徑上的最大邊權 → 求重構樹上 u, v 兩個點的 LCA。
只保留邊權小於等於 x 的邊形成的樹 → 重構樹上點權小於 等於 x 的點的子樹。
Borůvka 演算法
前置知識
距離
（x1,y1）（x2,y2）
曼哈頓距離：|x1-x2|+|y1-y2|
切比雪夫距離：max(|x1-x2|,|y1-y2|
歐幾里得距離：√[(x1-x2)2+(y1-y2)2]
曼哈頓距離與切比雪夫距離的相互轉化
兩者之間的關係
我們考慮最簡單的情況，在一個二維坐標系中，設原點為(0,0)。
如果用曼哈頓距離表示，則與原點距離為1的點會構成一個邊長為2–√2的正方形。
如果用切比雪夫距離表示，則與原點距離為1的點會構成一個邊長為2的正方形。
對比這兩個圖形，我們會發現這兩個圖形長得差不多，他們應該可以通過某種變換互相轉化。
事實上,
將一個點(x,y)的坐標變為(x+y,x−y)後,原坐標系中的曼哈頓距離 =新坐標系中的切比雪夫距離。
將一個點(x,y)的坐標變為(（x+y）/2,（x−y）/2) 後,原坐標系中的切比雪夫距離 = 新坐標系中的曼哈頓距離。
（注意：切比雪夫距離轉曼哈頓距離要再除以二）
用處
切比雪夫距離在計算的時候需要取max，往往不是很好優化，對於一個點，計算其他點到該的距離的複雜度為O(n)。
而曼哈頓距離只有求和以及取絕對值兩種運算，我們把坐標排序後可以去掉絕對值的影響，進而用前綴和優化，可以把複雜度降為O(1)。
第三種求最小生成樹的演算法，雖然比較冷門但是很多題需要用到這個演算法。
我們維護當前形成的所有連通塊，接下來對於每一個連通塊，找到邊權最小的出邊，然後合併兩個連通塊。
不斷重複這個操作，直到整張圖變成一個連通塊。
由於每次操作連通塊數量至少減半，所以時間複雜度最壞為 O((n + m) log n)，隨機圖的話複雜度可以降到 O(n + m)。
Tarjan演算法
Tarjan 演算法不是某個特定的演算法，而是一群演算法。
強連通分量
割點/割邊/橋
點雙連通分量
邊雙連通分量
離線 O(n) 求 LCA
此外還有很多 Tarjan 獨立/合作創造的演算法：
Splay，LCT， 斐波那契堆，斜堆，配對堆，可持久化數據結構，……
有向圖——強連通分量
如果對於兩個點 u, v，同時存在從 u 到 v 的一條路徑和從 v 到 u 的一條路徑，那麼就稱這兩個點強連通。
如果一張圖的任意兩個點均強連通，那麼就稱這張圖為強連通圖。
強連通分量指的是一張有向圖的極大強連通子圖。 （極大≠最大）
Tarjan 演算法可以用來找出一張有向圖的所有強連通分量。
我們用 dfs的方式來找出一張圖的強連通分量。
建出 dfs 樹，記錄一下每一個節點的時間戳(dfn)，然後我們考慮強連通分量應該滿足什麼條件。
我們可以再記錄一個 low 數組，表示每一個點能夠到達的最小的時間戳，如果一個點的 dfn=low，那麼這個點下方就形成了一個強連通分量。
在 dfs 的過程中，對於 (u, v) 這條邊：
若 v 未被訪問，則遞歸進去 dfs 並且用 low[v] 更新 low[u]。
若 v 已經被訪問並且在棧中，則直接用 dfn[v] 更新 low[u]。
最後如果 dfn[u]=low[u]，則直接把棧中一直到 u 的所有點 拿出來作為一個強連通分量。
時間複雜度 O(n)。
有向圖——縮點
跑出來強連通分量之後，我們可以把一個強連通分量看成一 個點。
接下來枚舉所有的邊，如果是一個強連通分量里的就忽略， 否則連接兩個對應的強連通分量。這個操作稱為縮點。
縮點後就變成了一張有向無環圖，處理連通性問題的時候會方便很多。
無向圖——割點
對於一張無向圖，我們希望求出它的割點。
無向圖的割點定義為刪掉這個點之後，連通塊數量會發生改變的點。
類比上面，我們還是記錄一下 dfn（時間戳）和 low。
對於 u 的一個子節點 v，若 dfn[u]≤low[v]，則 u 是割點（因 為 v 無法繞過 u 往上走）。
不過需要注意兩點：
根節點不能用這種方法，而是應該看它的子節點數量是否大於等於 2，如果是那麼根節點就是割點。
枚舉出邊的時候要特判掉父子邊的情況。
無向圖——橋
無向圖的橋定義為刪掉這條邊後，連通塊數量會發生改變的邊。
和上面的方法幾乎一模一樣，唯一的區別是判斷dfn[u]<low[v]而不是dfn[u]≤low[v]。（如果從 v 出發連 u 都無法 到達，那麼 (u, v) 就是一個橋邊）
甚至連根節點都不需要特判了。
無向圖——點/邊雙連通分量
如果兩個點之間存在兩條點互不相交的路徑，那麼就稱這兩個點是點雙連通的。
如果兩個點之間存在兩條邊互不相交的路徑，那麼就稱這兩個點是邊雙連通的。
其餘的定義參考強連通分量。
割點將整張圖分成了若干個點雙連通分量，並且一個割點可以在多個點雙連通分量中。
而橋則把整張圖拆成了若干個邊雙連通分量，並且橋不在任意一個邊雙連通分量中。
魔改一下強連通分量演算法即可。
當然，無向圖也可以縮點，不過主要還是可以用來建圓方樹。
二分圖匹配
前置知識
匹配
在圖論中，一個匹配是一個邊的集合， 其中任意兩條邊都沒有公共頂點。
最大匹配
一個圖所有匹配中，所含匹配邊數最多的匹配， 稱為這個圖的最大匹配。
如果要求一般圖的最大匹配，需要用 O(n 3 ) 的帶花樹，至少 是 NOI+ 的演算法。在聯賽階段，我們一般只關注二分圖的匹配問題。
最大匹配——匈牙利演算法
完美匹配
如果一個圖的某個匹配中，所有的頂點都是匹配點，那麼它就是一個完美匹配。
二分圖
如果一個圖的頂點能夠被分為兩個集合 X, Y，滿 足每一個集合內部都沒有邊相連，那麼這張圖被稱作是一張二分圖。
（dfs可以判斷一張圖是否是二分圖）
交替路
從一個未匹配點出發，依次經過非匹配邊——匹配 邊——非匹配邊——……形成的路徑叫交替路。
增廣路
從一個未匹配點出發，依次經過非匹配邊——匹配 邊——非匹配邊——……——非匹配邊，最後到達一個未匹配點形成的路徑叫增廣路。
注意到，一旦我們找出了一條增廣路，將這條路徑上所有匹配邊和非匹配邊取反，就可以讓匹配數量+1。
匈牙利演算法就是基於這個原理。
假設我們已經得到了一個匹配，希望找到一個更大的匹配。
我們從一個未匹配點出發進行 dfs（深度優先搜索），如果找出了一個增廣路， 就代表增廣成功，我們找到了一個更大的匹配。
如果增廣失敗，可以證明此時就是最大匹配。
由於每個點只會被增廣一次，所以時間複雜度是 O(n(n + m))。
二分圖最大權匹配——KM 演算法
現在我們把所有的邊都帶上權值，希望求出所有最大匹配中權值之和最大的匹配。
我們的思路是給每一個點賦一個「期望值」，也叫作頂標函數 c，對於 (u, v) 這條邊來說，只有 c(u) + c(v) = w(u, v) 的時 候，才能被使用。
容易發現，此時的答案就是 ∑c(i)。
初始，我們令左邊所有點的 c(u) = maxv w(u, v)，也就是說最理想的情況下，每一個點都被權值最大的出邊匹配。
接下來開始增廣，每次只找符合要求的邊。我們定義只走這些邊訪問到的子圖為相等子圖。
如果能夠找到增廣路就直接增廣，否則，就把這次增廣訪問到的左邊的所有點的 c − 1，右邊所有點的 c + 1。
經過這樣一通操作，我們發現原來的匹配每一條邊仍然滿足條件。同時由於訪問到的點左邊比右邊多一個（其餘的都匹配上了），所以這樣會導致總的權值−1。
接下來再嘗試進行增廣，重複上述過程。直接這樣做時間復 雜度是 O(n 3 c) 的。（進行 n 次增廣，每次修改 c 次頂標，訪問所有 n 2 條邊）
優化
由於修改頂標的目標是讓相等子圖變大，因此可以每次加減 一個最小差值 delta。這樣每次增廣只會被修改最多 n 次頂標，時間複雜度降到 O(n 4 )。
注意到每次重新進行 dfs（深度優先搜索） 太不優秀了，可以直接進行 bfs， 每次修改完頂標之後接著上一次做。時間複雜度降到 O(n 3 )。
技巧
最小點覆蓋
選取最少的點，使得每一條邊的兩端至少有一 個點被選中。
二分圖的最小點覆蓋 = 最大匹配
證明
1.由於最大匹配中的邊必須被覆蓋，因此匹配中的每一個點對 中都至少有一個被選中。
2.選中這些點後，如果還有邊沒有被覆蓋，則找到一條增廣路，矛盾。
最大獨立集：選取最多的點，使得任意兩個點不相鄰。
最大獨立集 = 點數-最小點覆蓋
證明
1.由於最小點覆蓋覆蓋了所有邊，因此選取剩餘的點一定是一個合法的獨立集。
2.若存在更大的獨立集，則取補集後得到了一個更小的點覆蓋，矛盾。
最小邊覆蓋：選取最少的邊，使得每一個點都被覆蓋。
最小邊覆蓋 = 點數-最大匹配
證明
1.先選取所有的匹配邊，然後對剩下的每一個點都選擇一條和 它相連的邊，可以得到一個邊覆蓋。
2.若存在更小的邊覆蓋，則因為連通塊數量 = 點數-邊數，這 個邊覆蓋在原圖上形成了更多的連通塊，每一個連通塊內選一條邊，我們就得到了一個更大的匹配。
最小不相交路徑覆蓋：一張有向圖，用最少的鏈覆蓋所有的點，鏈之間不能有公共點。
將點和邊分別作為二分圖的兩邊，然後跑匹配，最小鏈覆蓋 = 原圖點數-最大匹配。
最小可相交路徑覆蓋：一張有向圖，用最少的鏈覆蓋所有的 點，鏈之間可以有公共點。
先跑一遍傳遞閉包，然後變成最小不相交路徑覆蓋。
補充
小黃鴨調試法
當你的程式碼出現問題的時候，
將小黃鴨想像成你的同學，
將你的程式碼一行一行地講給它，
也許講到一半你就知道問題出在哪了。
不要定義以下變數名
next,abs,x1,y1,size……
並非原創，僅是整理，請見諒
