[ Strongly Connected Component - Tarjan & Kosaraju ] 強連通分量的兩種做法(dfs)

一張有向圖，找到所有的 Strongly Connected Component ；亦可進一步收縮所有的 SCC 、收縮所有的環，讓原圖變成 DAG 。

方法1-Tarjan法
跟BCC差不多，直接提供模板:

方法2-Kosaraju
對圖做一次DFS，求他的時間戳，再把圖反向，逆著時間戳進行第二次DFS，所遍歷的點就會是同一個SCC，記得不要走重複的點
以下提供模板:

用法:

[ Bridge & Bridge-connected Component ] 橋和橋連通分量(BCC)

只要從一張無向圖上移除了橋，就會讓這張圖分離成更多部分，呈現不連通的狀態。
注意！必須要考慮重邊的問題:

1. 對於有向圖的強連通分量，重邊是沒有影響的，因為強連通只要求任意兩點可以互相連通
2. 對於無向圖的點雙連通分量，重邊也是沒有影響的，因為點雙連通要求是任意兩點之間至少存在兩條點不重複的路徑，對邊的重複並沒有要求
3. 對於無向圖的邊雙連通分量，重邊就有影響了，因為邊雙連通要求任意兩點之間至少存在兩條邊不重複的路徑

這裡提供模板:

一張無向圖上，不會產生橋的連通分量，稱作橋連通分量，或是橋雙連通分量
這裡提供模板，code跟橋差不多，只是需要用堆疊去記錄當前節點而已:

[ Articulation Vertex ] 割點

關節點(割點)是讓一張無向圖維持連通，不可或缺的點。只要從一張無向圖上移除了關節點（以及與之相連的邊），就會讓這張圖分離成更多部分，呈現不連通的狀態。
存在一種線性算法找出一張圖所有的割點，一個dfs就能解決了

以下提供模板:

[ round-off error eps ] 浮點數誤差模板

有些計算幾何的過程中會產生捨位誤差，這時候就需要決定一個很小的數，去避開這個捨位誤差問題，我們稱那個很小的數為EPS

• A < B ....... A - B < - EPS
• A > B ....... A - B > EPS
• A == B ....... abs(A - B) <= EPS
• A <= B ....... A - B <= EPS
• A >= B ....... A - B >= - EPS

因為我的計算幾何模板在實作時是用template實作的，所以如果需要處理浮點數誤差時，需要傳入一個新的資料結構，所以寫了這份模板

[ long long multiply long long mod long long ] long long 乘 long long 模 long long不溢位算法

這標題有點長，不過也很清楚的顯示了這篇的重點，所以就直接附模板吧
如果a,b<m的話a%=m,b%=m;可以拿掉沒關係

code(比較慢，但適用範圍更大，算法取自維基百科:同餘):

[ Maze generation-Randomized Kruskal's algorithm ] 迷宮生成-隨機Kruskal算法

說得通俗點，就是"隨機拆牆"。
一開始假設所有牆都在，也就是圖的每個點都不連通。如果當前不滿足“任意兩個格子間都有唯一路徑”，那麼就隨機選擇一堵牆，要求牆兩端的格子不連通，即它們對應的兩個頂點在兩個不同的連通分量。把這堵牆拆掉，即在後牆兩端的格子對應的頂點間建立一條邊。重複作下去，直到所有的點都在同一個連通分量裡面。
會發現這就是隨機合併點的Kruskal演算法，需要用到並查集

範例生成圖:
＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃
＃　　　＃　　　　　　　＃　　　＃　　　　　　　＃
＃＃＃　＃　＃　＃　＃＃＃　＃＃＃＃＃＃＃　＃＃＃
＃　　　　　＃　＃　　　＃　　　＃　＃　　　　　＃
＃＃＃＃＃＃＃＃＃　＃＃＃　＃　＃　＃＃＃＃＃　＃
＃　　　　　　　＃　＃　　　＃　　　＃　　　　　＃
＃＃＃　＃＃＃　＃　＃　＃　＃＃＃　＃＃＃　＃＃＃
＃　　　＃　　　＃　　　＃　　　＃　　　　　　　＃
＃＃＃　＃　＃＃＃＃＃　＃＃＃　＃＃＃＃＃　＃＃＃
＃　　　＃　　　　　　　＃　＃　　　　　＃　＃　＃
＃＃＃＃＃＃＃　＃　＃＃＃　＃　＃＃＃＃＃＃＃　＃
＃　　　＃　＃　＃　　　＃　　　　　　　＃　＃　＃
＃　＃＃＃　＃＃＃　＃＃＃　＃　＃＃＃＃＃　＃　＃
＃　＃　　　　　＃　＃　　　＃　＃　＃　＃　＃　＃
＃　＃　＃＃＃　＃　＃＃＃　＃＃＃　＃　＃　＃　＃
＃　＃　＃　　　　　＃　　　＃　　　　　　　　　＃
＃　＃　＃＃＃　＃＃＃＃＃＃＃＃＃　＃　＃＃＃＃＃
＃　　　＃　　　＃　＃　＃　　　　　＃　　　＃　＃
＃＃＃＃＃＃＃　＃　＃　＃　＃　＃＃＃　＃＃＃　＃
＃　　　　　＃　　　　　　　＃　　　＃　　　　　＃
＃　＃　＃＃＃＃＃　＃＃＃＃＃＃＃＃＃　＃　＃＃＃
＃　＃　　　　　　　　　　　　　　　＃　＃　　　＃
＃＃＃　＃　＃　＃＃＃　＃　＃＃＃＃＃＃＃　＃＃＃
＃　　　＃　＃　　　＃　＃　　　＃　　　　　　　＃
＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃

code(n,m必須是奇數):

[ min-max heap ] 最小-最大堆

最小-最大堆(Min-Max Heaps)是一個完整二元樹。此二元樹是交替的階層方式呈現，分別為最小階層 ( min level ) 和最大階層 ( max level ) ，這裡實作樹根為最小鍵值。

最小-最大堆是一種堆積支援以下幾種操作:

1. 求最大值 - max()
2. 求最小值 - min()
3. 刪除最大值 - pop_max()
4. 刪除最小值 - pop_min()
5. 元素入堆 - push()

詳細演算法可以參考原始論文
Min-Max Heaps and Generalized Priority Queues

如果不懂敘述就看code吧
以下提供模板: