Google Drive
Gist
Clipboard
Introduction to Competitive Programming
03/01
一種對有向圖的排序方式
有 \(n\) 個節點，編號從 \(1\) 到 \(n\)，要制定一種排序使得
如果有一條邊 a \(\rightarrow\) b, 在排序中 a 就會比 b 還前面。
如果圖不是有向無環圖（DAG），不存在拓撲排序。
DFS/BFS 都可以做，這邊說 BFS 的
可以觀察到入度為 0 的點在拓撲排序中會在最前面，
放完之後，把 4, 8 連出去的邊移除
接著就繼續將入度為 0 的點加入 queue 裡面， queue 是空的就做完了。
一開始建圖時，可以用一個陣列 deg[MXN] 紀錄每個點入度多少
for(int i=0;i<m;i++){
cin >> u >> v; //點 u 連到點 v
edge[u].push_back(v);
++deg[v];
}
建完圖之後，開始拔入度為 0 的點，可以用 queue 儲存要拔掉的點，依序拿出來
for(int i=0;i<n;i++){
if(!deg[i]) que.push(i); // 度數為 0 時推入佇列中
}
每次從 queue 裡面取出一個點，將他連到的點入度都減 1，減的時候順便確認那個點是否入度為 0 了
for(int i:edge[u]){
--deg[i];
if(deg[i] == 0){ // 當度數為 0 時，將節點推入佇列
que.push(i);
}
}
拔邊的時候每條邊、點都會經過至少一次
\(O(N+M)\)
其實也不一定要用 queue 來實作，也可以用其他可以 push 跟 pop 的資料結構，只要是入度為 0 的點，都可以被拿來進行拓撲排序，順序不會影響正確性。
題意：給 n 個工作跟 m 組 pair
每組 pair 代表的是兩個工作的先後順序，前面的會比後面的早做
詢問任意一組合理的工作順序。
可以發現每組 pair 代表的是有向圖的一條邊，我們再圖上求出拓撲排序就可以找到合理的工作順序了。
題意：給一張有 n 個點 m 條邊的有向圖 (不一定連通)，給編號 1 ~ n 的點都貼上帶有數字的標籤，邊 u \(\rightarrow\) v 的標籤 \(label_u\) 要小於 \(label_v\)。
最後依照編號順序輸出標籤的數字，且字典序要最小。
直接拓撲加上優先佇列（由編號小的先拿）？
如果用正向拓撲加上優先佇列的話，下圖的答案會是
6 5 2 1 4 3?
但答案應該要是
6 3 5 4 2 1
如果有編號大的數字指向編號小的數字，可能讓編號小的數字較晚被分配到數字，導致字典序變大。
如果對原圖建反圖，然後由大到小分配數字，這樣就只會造成編號大的數字比較晚分配到數字，字典序就會是最小的。
可以觀察到平常的 DP 我們會用到之前用過的答案，如果將這個過程轉換成圖的話，就會變成一張 DAG
反之，如果圖是一張 DAG，依據題目也可以嘗試去轉換成 dp。
題意：
一個遊戲有 \(n\) 個關卡，有 \(m\) 個傳送器連結。
第 \(i\) 個傳送器會從關卡 \(u_i\) 傳送到關卡 \(v_i\)
詢問從第 1 個關卡到第 n 個關卡有幾種方式？
保證關卡不會經由傳送器回到自己(也就是沒有環)
傳送器只能從關卡 u 到關卡 v，其實就是在說這張圖是一張有向圖，而題目有說沒有環，所以這就會是一張有向無環圖(DAG)。
dp[i] 代表的是走到第 \(i\) 個關卡有幾種方式
而他的 dp 式也可以推成 \(dp[i] = \sum\limits_{edge(i, j)} dp[j]\)
int dfs(int x) {
if(ans[x] != 0) return ans[x]; // 點已經被走過就回傳答案
int res = 0;
for(int i = 0; i < a[x].size(); i++) {
res = (res + dfs(a[x][i]) % 1000000007;
}
return ans[x] = res;
}
題意： 給一張 N 個點 M 條邊的 DAG，詢問從每個點作為起點，可以走到的節點數量
\(1 \le n \le 5 * 10^4\)
\(1 \le m \le 10^5\)
跟上一題不一樣的是，上一題要求的是到某個節點的方式有幾種，而這題要求的是可以走到幾個節點，因為沒有直接的結合律，好像沒容易簡單用 dp 去記錄答案。
dp 改成記錄每一個點可以走到哪些點，
dp[1] = dp[2] \(\cup\) dp[3] \(\cup\) 1
所以可以對每個節點都開一個大小為 n 的陣列，記錄這個節點可以走到哪些節點
轉移式
\(dp[i] = dp[i] \cup dp[j]\ \forall \ (i \rightarrow j)\)
不過這樣做的時間複雜度會是 \(O(n (\)陣列大小\() * m (\)更新次數\())\) = \(O(5 * 10^9)\) 還是會超過一秒。
可以用 bitset 去優化轉移的時間，可以發現兩個 dp 取交集時，等價於用 bitset 做位元 or，我們就可以用 bitset 壓一下常數。
在 bitset 優化後，對陣列取交集變成 \(O(\frac{n}{32})\)
最後的複雜度變成 \(O(\frac{5 * 10^9}{32}) \approx O(10^8)\)，就會 AC 了！
bitset<MXN> dp[MXN];
void dfs(int x) {
v[x] = 1;
dp[x][x] = 1;
for(int i : edge[x]) {
if(!v[i]) dfs(i);
dp[x] |= dp[i]; // 取兩個集合的交集
}
};
在一個圖中找環主要有兩種方式
拓撲排序的做法就跟前面一樣，可以觀察到如果一張圖有環，做完拓撲之後：
可以根據以上性質用拓撲排序去找圖有沒有環
做完拓撲排序後如果有點沒有被推入佇列就代表圖內有環。
dfs 時，會將圖變成一棵樹，我們利用的是這顆樹與其他邊的性質，可以分成有向圖跟無向圖兩種。
dfs 時會將無向圖的邊分成 tree edge 跟 back edge，
可以很直覺的發現，當一張無向圖有 back edge，就會有環，所以我們在 dfs 時，只要走到同一個點兩次，就可以確認這個圖有環
int vis[N];
bool dfs(int x, int v) {
if(vis[x]) return true; // 遇到祖先就代表有環，回傳 true
vis[x] = 1;
for(auto i:g[x]) {
if(i == v) continue;
if(dfs(i, x)) {
return true;
}
}
return false;
}
跟無向圖一樣，如果有回邊的話也會有環。
不過 dfs 時會把邊分成四種，除了原本的兩種，還多了 cross edge 跟 forward edge，會留到之後再做介紹。
至於要怎麼判斷有向圖的回邊呢？
可以把節點分成三種，還沒走過的、下面節點還沒走完的、下面節點已經走完的，這樣子在 dfs 時遇到下面節點還沒走完的時，就代表走的那條邊是回邊了。
bool dfs(int x, int v) {
if(vis[x] == 1) return true; // 當走到還沒走完的點，就代表有環
if(vis[x] == 2) return false; // 走到已經走完的節點，當沒事發生
vis[x] = 1; // 標記這個點還沒被走完
for(auto i:g[x]) {
if(dfs(i, x)) {
return true;
}
}
vis[x] = 2; // 標記這個點已經被走完
return false;
}
如果是要找環的路徑，可以將 dfs 改一下，由於環就是回邊造成的，因此環的路徑就是回邊的點到現在所在的點的這條路徑，只要記錄 dfs 樹每個節點是從哪條邊走過來的，就可以找到圖上的一個環。
int vis[], suc[];
int dfs(int x, int v) {
if(vis[x]) return x;
suc[x] = v;
vis[x] = 1;
for(auto i:g[x]) {
int tmp = dfs(i, x); // x 的祖先，
if(tmp) {
int now = x;
while(now != tmp) { // 找從 x 到 tmp 的路徑
cout << now << ' ';
now = suc[now];
}
cout << tmp << ' ' << x << '\n';exit(0);
}
}
return 0;
}
有向圖留給大家自己練習>.<
在所有橋只能走過一遍的情況下，如何才能將所有橋走遍。
Note:
星報氣流展
現在的七橋：
要怎麼找出一條歐拉路徑/迴路呢？
可以先從判斷一張圖有沒有歐拉路徑開始
一樣分成有向圖和無向圖的判斷方式
可以從節點的角度來觀察，每個點都有不同的度數，而度數代表的是可以進出這個點幾次，如果一個點的度數是奇數，如果要走完這樣的節點的邊，需要進出 \(\lfloor \frac{n}{2} \rfloor\) 次，且最後會停在這個節點，反之，如果度數是偶數，則是要進出 \(\frac{n}{2}\) 次，且除了起始點以外，會離開這個節點。
一張無向圖要有歐拉迴路，對點的要求是每個節點進出都不會被卡在裡面，如果有度數為奇數的點，走完邊的結果會是卡在裡面，因此無向圖歐拉迴路需要無向圖節點的度數都是偶數。
一張無向圖要有歐拉路徑的條件比迴路寬鬆一點，由於你可以從一個點開始，另一個點結束，所以你可以同時有兩個度數為奇數的點，一個點當起點，另一個點當終點
有向圖跟無向圖不同的是要完整走完一個節點的邊，需要的是入度與出度相同，只要滿足這條件，就有可能會有歐拉路徑。
與無向圖相同，可以從一個點開始，另一個點結束，因此有向圖有歐拉路徑的條件是一個點的出度等於入度減一，另一個點的入度等於出度減一，這樣就可以從入度等於出度減一的點作為起點，出度等於入度減一的點作為終點。
歐拉證明了只要滿足以上條件，就一定可以構造出一個歐拉路徑/迴路，統整一下歐拉路徑/迴路成立的條件。
| 歐拉迴路 | 歐拉路徑 | |
|---|---|---|
| 無向圖 | 所有點的度數為偶數 | 度數為奇數的點數量不超過2 |
| 有向圖 | 所有點入度等於出度 | 全部點的入度出度一樣 或剛好一個點出度-1=入度 另一點入度-1=出度， 其他點入度等於出度 |
並且圖連通
從 入度等於出度減一 的點開始作為起點，並開始 dfs，每次選一條新的邊繼續遞迴，dfs 結束後將點加入路徑中，遞迴後將路徑反轉就是答案了。
vector<int> path;
void dfs(int x){
while(!edge[x].empty()){
int u = edge[x].back();
edge[x].pop_back();
dfs(u);
}
path.push_back(x);
}
int main(){
build_graph();
dfs(st);
reverse(path.begin(),path.end());
for(int i:path) cout<<i<<' ';
cout<<endl;
}
給定一堆英文單字，詢問是否有一種單字的排列，可以讓連續兩個單字頭尾的字母都一樣
可以將題目轉換成圖論問題，將每個單字轉換成字首字母到字尾字母的有向邊，這樣題目就會變成在找歐拉路徑了。
de Bruijn 序列是一個字串，這個字串包含了長度為 n 且每個字母有 k 種可能的字串
例如，當 n = 3, k = 2 時，de Bruijn 序列的其中一種可能性是 0001011100，他有 000, 001, 010, 011, 100, 101, 110和111 的子字串
通過一些證明，de Bruijn 序列的長度固定會是 \(k^n + n - 1\)
首先，我們對所有長度為 n - 1 的子字串作為節點建立一張圖
一樣以 n = 3, k = 2 為例：
每個節點連出連出的邊會有 k 種，而連到的節點則是將本來所在節點的第一個 bit 刪掉，並在後面將邊上代表的 bit 放在最後面。
得到 de Bruijn 序列的方式就是，從任意一個點開始，找到圖的歐拉迴路， de Bruijn 序列就會是起始節點的字串加上邊上所有的bit。
為什麼這樣會是好的呢，可以觀察到，序列 abc 可以通過 ab 節點的前面兩個節點連接的邊構成，而 c 就會是連出去的邊，我們只要找到任意的歐拉路徑，代表就可以構出所有長度為 n 且有 k 種可能性的子字串
n = n, k = 2 的圖的建圖方式
for (int i = 0; i < (1<<(n-1)); i++){
v[i].push_back(((i<<1))&((1<<(n-1))-1));
v[i].push_back(((i<<1)+1)&((1<<(n-1))-1));
}
把圖建完跑一遍歐拉路徑就是一組合法解了
給定一張圖，是否有一條路徑恰好走過所有節點剛好一次。
與歐拉路徑類似，只是要遍歷的變成了點
與歐拉路徑的問題不同，經過證明，漢米爾頓路徑是 NP-C 的問題，沒有多項式時間的解決方式，
最直接的做法就是對點集找全排列 (next_permutation)，對每種排列花 \(O(n)\) 時間看可不可行，時間複雜度 \(O(n * n!)\)
由於每個點只能走過一次，所以可以將點集分成 已經走過的、還沒走過的
定義 dp[i][{s}] 為當前在點 i，且已經拜訪過 {s} 這些點了
實作時由於 n 不會很大， {s} 會用狀態壓縮的方式去實現，用整數的 bit 去記錄 s 的集合內含有哪些數字。
i = 3，{s} = 11001 代表的就是已經走過 0、3、4 三點，且目前在 3 的位置
狀態轉移式：當有一條 i 到 j 的邊且 j 不屬於 s 時 \(dp[j][{s} \cup j] = dp[i][{s}]\)
if(((1 << i) & s) && !((1 << j) & s)) {
dp[j][s | (1 << j)] = dp[i][s];
}
for(int i = 1; i < (1 << n); i++) {
for(int j = 0; j < n; ++j) {
if(!((1 << j) & i)) {
for(int k = 0; k < n; k++) {
if(j == k) continue;
if((1 << k) & i) {
dp[j][i | (1 << j)] = dp[k][i];
}
}
}
}
}
複雜度: \(O(n^22^n)\)
給定一個完全圖，每個邊都有邊權，求每一個點訪問剛好一次且最後要回到初始地的最短距離。
可以看出這個就是帶權的漢米爾頓迴路，所以也是以類似的方式去實作，放在習題讓大家自己去練習看看^^
deadline: 3/8
link: this
-
Any changes
Be notified of any changes
-
Mention me
Be notified of mention me
-
Unsubscribe
Subscribe