\( \newcommand{\ord}[1]{\mathcal{O}\left(#1\right)} \newcommand{\abs}[1]{\lvert #1 \rvert} \newcommand{\floor}[1]{\lfloor #1 \rfloor} \newcommand{\ceil}[1]{\lceil #1 \rceil} \newcommand{\opord}{\operatorname{\mathcal{O}}} \newcommand{\argmax}{\operatorname{arg\,max}} \newcommand{\str}[1]{\texttt{"#1"}} \)

2016年1月31日 星期日

[ Miller-Rabin Strong Probable-prime Base ] 質數測試算法保證long long範圍內正確

這本來是隨機演算法,但是已經有一些人,找出一些特定底數,保證判定結果在某些範圍內正確。

如果是unsigned long long範圍內東西記得要用long long乘long long mod long long 的模板
這裡的範例已經加在code裡了,如果不需要可以把它拿掉(zerojudge a007不拿掉會變慢)

code:

2016年1月27日 星期三

[ Biconnected Component ] 雙連通分量(BCC)

一張無向圖上,不會產生割點的連通分量,稱作「雙連通分量」。一張無向圖的雙連通分量們,通常會互相重疊,重疊的部分都是原圖的割點。
可以利用堆疊+tarjan算法快速地找出那些點是割點和雙連通分量
以下提供模板:

2016年1月3日 星期日

[ 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就能解決了

以下提供模板: