Advanced Competitive Programming

Advanced 國立成功大學 ACM-ICPC 程式競賽培訓隊 nckuacm@imslab.org Department of Computer Science and Information Engineering National Cheng Kung University Tainan, Taiwan

Week 5 Sorting & Graph 排序離散化一些基礎圖論

Outline 排序 - Merge Sort - Counting Sort 離散化基礎圖論 - Dfs - Bfs - Disjoint Set & Union

Sort

排序? 那是什麼? 可以吃嗎? 簡單來說, 就是排序像是把 1,4,5,3,2 排成 1,2,3,4,5

Sorting Algorithm Bubble Sort Merge Sort Counting Sort STL Sort

Bubble Sort 從最基礎的開始

Bubble Sort 1. 比較兩個相鄰的元素, 前面的比較大就 swap 2. 重複動作 1 直到序列結束 3. 重複以上動作直到序列不需要再做調整

code

Bubble Sort Animation

分析一下複雜度因為序列長度為 N, 所以內層迴圈要跑 N 次 worst case 可能需要跑 N 次內層迴圈所以複雜度為 O(N 2 )

Merge Sort Deja vu! 加速囉

Merge Sort 分治的一種不斷地把序列拆成左右子序列, 並對他們遞迴將兩邊的結果合併

For Example

code #1 - Basic version

code #2 - advanced version

分析一下複雜度每次都會把序列長度砍半也就是說有 logn 層每一層最差需要處理 N 個數字複雜度為 O(NlogN)

Counting Sort はやく! もっとはやく! ( 快! 還要更快! )

Counting Sort 計算各個元素出現次數

code

分析一下複雜度因為要把整個陣列掃過一次 O(N) 假設值域大小為 K, 最後還要掃過整個值域 O(K) 總複雜度 O(N + K)

Discretization 既然學完排序了

假設今天有個題目請計算出個元素出現的次數 1 N 10 5, S i 10 9 ( 沒錯! 有負數!)

沒錯! 就是離散化! 顧名思義只在乎元素之間的關係, 並不在乎差距像是我們可以把 1,5,9,11,2000 轉換成 0,1,2,3,4 於是我們就不用怕負數了 <3 不過還是可以用 map 就是了啦 ( 小聲

先備知識 STL 函數 unique sort( 或是你要自己手寫也可以啦 ) 二分搜通常我是用 lower_bound

code

基礎圖論

名詞解釋圖 : 由數個節點以及邊組成環 : 一個節點可以由不重複的路徑回到自己, 則稱這條路徑為環樹 : 沒有任何環的聯通圖聯通塊 : 一群點中, 所有點都可以直接或間接連接到其他點

圖的儲存鄰接矩陣 G[u][v] 表示 u 與 v 之間有一條邊存在鄰接表把 u 會連接到的點都 push 進去 G[u] 假設有一條單向邊從 u 到 v G[u].push_back ( v ); 假設有一條雙向邊於 u, v 之間, 則需要 G[u].push_back ( v ), G[v].push_back ( u );

假設現在有 n 個點 m 條邊

如果還有權重的話

Searching

dfs 全名 :Depth-First Search, 深度優先搜尋由 Hopcroft & Tarjan 提出把根節點塞入 stack 中 while ( stack!= empty() ) 取出第一個點, 把未遍歷過的相鄰節點塞進 stack

code

bfs 全名 :Breadth-First Search, 廣度優先搜尋法把根節點塞入 queue 中 while ( queue!= empty() ) 取出第一個點, 把未經歷過的相鄰節點塞進 queue

code

Disjoint Set

Disjoint Set 可以在良好的複雜度內, 查詢兩個元素是否在同一個集合同一個元素不會同時出現在兩個集合內

Disjoint Set 操作查詢元素所屬組別加入新元素進入集合合併兩個集合查詢集合大小

Disjoint Set 概念用一顆樹表達一個組別如果兩個相異元素根節點相同, 則兩元素屬於同一個集合

Disjoint Set Initialization

Disjoint Set Find

欸, 好像怪怪的

假設一下想一下, 如果這一個結構是 1 2 3 4... n 那麼每次 find ( 1 ) 就要跑 n 次, 複雜度 O(n) 聽起來很爛

路徑壓縮因為第一次查詢的時候就已經知道最頂端的節點是什麼了所以記錄下來, 下一次就省掉許多時間了有數學證明可以把複雜度從 O(N) 壓到 O(α(N)) α 指的是反阿克曼函數, 簡單來說就是成長速度非常慢的函數

Disjoint Set Union

codes on github https://github.com/miohitokiri5474/codesbackup/tree/mas ter/ncku-icpc/2020/week5 https://ppt.cc/fkpjix

Topological Sort

點的度數在一張圖中, 每個節點都有它的度數, 一個節點的度數代表這個節點連接幾條邊如右圖, 點 1 的度數為 3, 點 4 的度數為 2, 點 5 的度數為 0

入度 & 出度但如果這是一張有向圖, 又可以將其細分為入度與出度, 入度就是連進這個節點的邊, 出度就是從這個點連出去的邊如右圖, 點 1 的入度為 1 出度為 2, 點 4 的入度為 1 出度為 1, 點 5 的入度為 0 出度為 0

Topological Sort 給定一張有向圖, 你要為所有節點訂定一個順序 {v 1, v 2,, v n }, 且這個順序滿足 i j 皆不存在從 v j 走到 v i 的路徑, 則此順序就是這張圖的拓樸排序

Topological Sort 如下圖中, {1,2,4,3,5,7,6} 就是一組合法的拓樸排序, 因為不存在任一組 i j 且有任一條路徑可以從 v j 走到 v i

Topological Sort 換個說法, 一個點如果要被排進序列時, 所有指向它的點都必須被排進去了, 以下圖為例點 2 必須等點 1 被排進去後才能被排進去點 3 必須等點 2 與點 4 被排進去後才能被排進去一張圖可能存在多組拓樸排序

做法那麼做法呼之欲出了, 只要某個點的入度為 0 時, 這個點就可以被排進去拓樸序列

做法只要每次都將入度為 0 的點排進拓樸序列尾端, 並將該點及其連出去的邊移出這張圖, 重複下去直到圖上所有點都被移除時, 就完成該圖的拓樸排序了實作過程可以使用 stack 或 queue 本篇教學使用 queue

做法只要每次都將入度為 0 的點放在當前序列尾端, 並將該點移出圖中, 重複下去直到圖上所有點都被移除時, 就完成該圖的拓樸排序了

做法只要開一個陣列記錄每個節點的入度, 在每一次要拔一個點時, 將該點指到的所有點入度都減 1, 如果那個點入度為 0 時, 將它丟進 queue 中演算法的複雜度 : 遍歷所有點, O(V) 遍歷所有邊, O(E) 總複雜度, O(V + E)

Topological Sort 欸那一張圖一定有拓樸排序嗎? 其實不一定可以看看右圖

Topological Sort 當一張圖出現環時, 這張圖不存在拓樸排序在程式中, 當你的 queue 中沒任何元素且整張圖未遍歷完時, 這張圖不存在拓樸排序一張圖存在拓樸排序若且唯若這張圖為有向無環圖, 通常簡稱為 DAG(Directed Acylic Graph)

Source Code

Questions?