---
title: MDCPP基礎圖論
tags: MDCPP
image: https://i.imgur.com/NZiHUtv.jpg
slideOptions:
transition: 'slide'
slide: data-background="https://i.imgur.com/NZiHUtv.jpg"
---

<style>
body{
background-attachment: fixed;
background-repeat: no-repeat;
background: -webkit-linear-gradient(left, #ffffff,rgba(51,51,51,0.3)), url("https://i.imgur.com/wuYV61U.jpg") center no-repeat fixed;
};
</style>

#### MDCPP競賽班講義
## 基礎圖論

---

## [先備知識](https://www.csie.ntu.edu.tw/~sprout/algo2020/ppt_pdf/week04/graph.pptx)

---

## 深度優先搜索 DFS

有路的話就繼續走，直到死路才回頭

----

### DFS求連通塊

----

[CSES Counting Rooms](https://cses.fi/problemset/task/1192)

要使用BFS也是可以，但DFS比較好寫和擴充，所以建議使用DFS。

----

### [小挑戰](http://www.usaco.org/index.php?page=viewproblem2&cpid=895)

**題目大意** : 找到周長與面積比值最小的連同塊

---

## 廣度優先搜索 BFS

先把附近的點走完才繼續往下走

----

### BFS求最短路

----

[倒水問題](https://www.luogu.com.cn/problem/P1432)

想想看為甚麼這是最短路問題?
題目裡有沒有可以當成節點的東西?

----

有時候，要能夠將問題轉化成圖論模型
就可以更容易的找到題目突破口

----

我們其實可以將狀態視為一個節點
像是這題的狀態就會是 2 個杯子分別裝的水量
可以表示成 $(a, b)$
用C++的話可以考慮寫成 pair

----

而邊的話 就是倒水的過程 (可以不用真的去建邊)
所以答案就會是 $(0, 0)$ 到 $(0, N)$ or $(N, 0)$ 的最短路

----

### 複雜度分析
在BFS或DFS時 複雜度通常就會是點和邊的數量
所以我們只要知道點數和邊數數量 就可以估算複雜度了

----

這題的點數 也就是所有狀態的總數 會是 $C_A \times C_B$
也就是兩個杯子的容量相乘 邊數也是同一個數量級

複雜度 $O(C_A \times C_B)$

----

### [小挑戰](https://dmoj.ca/problem/dmopc21c6p3)

### [挑戰](https://atcoder.jp/contests/abc241/tasks/abc241_f)

---

## 拓樸排序

----

### [排課問題](https://cses.fi/problemset/task/1679)

----

先把它變成圖論問題
如果 a 課程是 b 課程的必要先修課
則將 a 連一條有向邊到 b

----

問題變成 把所有點排序
使得所有邊 $u \rightarrow v$
$u$ 都排在 $v$ 的前面

----

也就是不會有邊往前指的情況


----

不難發現 如果存在環則必定無解
反之必有解

----

也就是說圖必須是一張DAG才會有解

Directed Acyclic Graph (有向無環圖)

---

### 如何求拓樸排序?

----

### BFS法

我自己取的 可以想成就是BFS的變化
主要想法是拔點

----

我們先想想 甚麼樣的點可以當作拓樸排序中第一個點?

----

其實就是沒有被限制的點(入度為0)
在沒有環的情況下
很明顯一定能找到至少一個這樣的點

----

那我們就先把一個入度為0的點選出來
當作拓樸排序的第一個
並把他連出去的所有邊拔掉
接下來就只要對剩下的圖繼續做一樣的事情就好了

----

### 實作

我們用一個資料結構來存放入度為0的點
(通常是用queue)
每次把一個點拔掉時 去更新所有他連出去的邊
查看有沒有新的入度為0的點 有的話就放入資料結構

----

### [範例代碼](https://cses.fi/paste/53131a900201bbdbda135/)

----

### DFS法

善用DFS的性質

----

先來想一個問題
一張DAG把所有邊反過來會變成甚麼?

----

~~還是一張DAG~~

----

也就是說 如果我們將原圖的邊反轉
且得到一組拓樸排序
這組拓樸排序的反轉後 也會是原圖的拓樸排序

----

我們善用DFS走到不能再走的性質
每次不能往前走時就將當前節點放入拓樸排序**尾部**

----

所以每次會從出度為0的點開始放入
也就是在求反圖的拓樸排序

----

寫法非常的簡潔

vector<int> g[mxN];
void dfs(int u) {
    for (int v : g[u]) {
        dfs(v);
    }
    topo.push_back(u);
}
// 最後要使用的時候記得將topo reverse

---

## DAG 上的動態規劃

----

其實所有動態規劃問題
都能先轉化成DAG 再對其進行DP

----

### 舉例

----

### LIS 最長遞增子序列

::: spoiler 轉換後
DAG上最長路徑問題
:::

----

### 01背包問題
求放入背包中的物品總價值最大值
::: spoiler 轉換後
DAG上帶權最長路徑問題
:::

----

### [盒子嵌套問題](http://cn.vjudge.net/problem/UVA-437)
這題不轉化成DAG好像會有點麻煩?

----

要怎麼在DAG上求最長路(DP)呢?

----

其實很簡單
按照拓樸排序的順序去DP就好

----

一條 $u \rightarrow v$ 的邊
就表示可以從 $u$ 轉移到 $v$

----

一樣可以分成兩種寫法
DFS和BFS法

----

### [實作練習](https://cses.fi/problemset/task/1680)

----

#### [參考程式碼 BFS](https://cses.fi/problemset/task/1680)
#### [參考程式碼 DFS](https://cses.fi/paste/1cadfb9813ec1cc737bd94/)

---

## 二分圖

----

### [練習](https://tioj.ck.tp.edu.tw/problems/1209)

----

### [挑戰](https://www.luogu.com.cn/problem/P1155)
### [挑戰](https://codeforces.com/contest/1635/problem/E)

---

## 歐拉路

https://www.itread01.com/content/1549588712.html

----

### [練習](https://cses.fi/problemset/task/1693)

小貼士 : 如過題目沒有保證圖是連通的記得要額外判斷