很多時候，圖論題目常常會在題目敘述中明講著「有一張圖」、或是「可以視作一個圖論的結構」等等。靠著這類資訊，我們很容易就可以往圖論的方向去思考。
不過在前面學習、寫習題的過程中，讀者可能會發現有幾道題目其實表面上並沒有「圖」，舉例來說：
給一個 $H \times W$ 的照片，- 代表空地，G 代表綠地，W 代表河流或湖泊，B 代表建築物。如果有兩格八方位相鄰的綠地，那麼兩格綠地會被計算為同一塊綠地。同樣地，八方位相鄰的空地也會被視為同一塊空地。現在需要知道城市中究竟有多少塊綠地和空地。
$1 \le W, H \le 100$
這是我們在圖論基礎用來講解 DFS 時的例題，從題目敘述中可以發現，確實沒有圖的存在。但同時我們也提到過，這題需要做的事情是把照片想像成圖、並把周圍八格想成鄰接的八條邊去處理連通塊問題。
這種把原本不是圖的物件，用圖的方式來表示的邏輯又被我們稱作「建圖」，是利用圖論解題時讓自己格外有圖論意識的解題手法。
不過上面這道例題感覺這就好像只是把「地圖」當成圖的感覺，差異似乎沒有這麼明顯。因此，本文章的目的就是要來帶大家看看，那些更不明顯、需要特別去做對應才能發現是圖論問題的「隱藏圖論問題」。
我們先來看看以下這道例題：
有 $N$ 張卡片，第 $i$ 張卡片的正面寫著顏色 $a_i$、背面寫著顏色 $b_i$。
對於每張卡片，你可以選擇要讓他的哪一面朝上。找出在最佳的策略下，最多可以有多少種不同的顏色朝上？
幾種不同數字聽起來很像某種貪心策略題，但仔細想一想之後就會發現，好像不管怎麼貪心都不太對勁？
這題讓人眼睛為之一亮的，就是只要使用非常巧妙的圖論對應方式就能秒殺這道題目。怎麼做呢？我們用以下方式建圖：讓每個不同的「顏色 $i$」對應到圖論上的「節點 $i$」；讓「一張卡片 $a_i, b_i$」，對應到圖論上的「一條連接 $a_i, b_i$ 的邊」，此時，在這樣的圖上的一個連通塊代表著什麼呢？
沒錯，當一個連通塊裡有 $k$ 個點，就代表連通塊裡面的「卡片」不論怎麼翻，都只能讓至多 $k$ 種「顏色」朝上而已。
反過來說，什麼情況下可能辦不到 $k$ 種顏色朝上呢？答案是，只要連通塊不是樹，就一定可以讓 $k$ 種顏色朝上，否則可以讓 $k-1$ 種顏色朝上！
證明也非常簡單，只要隨便找這個連通塊的一個有根生成樹，讓每個卡片所代表邊的以遠離根節點的那個顏色朝上，就可以讓 $k-1$ 種顏色朝上，此時如果還有多餘的一條邊能用，因為根節點是唯一沒有被用到的顏色，那我們就讓這條邊的任意一個節點是這棵生成樹的根節點，就可以讓這條邊補齊最後一個顏色了！
因此，這題的作法變得非常單純：建完圖之後，對於每個連通塊，將答案加上連通塊的 $\min(邊數, 點數)$。
是不是非常乾淨呢？
讓我們繼續看看下一題：
有 $n$ 個骨牌，每個骨牌上寫著兩個數字 $a_i$ 和 $b_i$。問你有沒有辦法把這些骨牌分成兩堆，使得同一堆內的骨牌包含的所有數字都相異？
看完了這道題目，肯定有一個相當直覺的「建圖方式」會浮現在腦中：把每個骨牌當成一個點，如此一來，只要兩個骨牌有相同的數字，在他們之間建一條邊就好。
這樣做的動機，當然是因為題目要求我們把骨牌分成兩邊，而因為被建邊的骨牌相當於不能在同一堆裡，所以自然而然的就變成了一道「二分圖判定」的題目。
可惜的是，骨牌的總數量高達 $2\times 10^5$，我們恐怕是沒辦法這麼暴力的建邊。
要解決這個問題其實有相當多種解決手法，但透過巧妙的建圖，其實可以得到一個相當簡短的結論！
我們不妨改成把數字當成點、並把骨牌當成邊。在這樣的模型底下，我們相當於要把邊上兩種顏色，使得同一種顏色的邊不能共點。而我們可以發現，只要一個點的「度數」超過 $2$，那連接這個點的三個骨牌就不可以被分成兩堆還不衝突，因此，所有點的「度數」都必須不超過 $2$。
這代表什麼呢？對於一張每個點度數都不超過 $2$ 的圖，他的每個連通塊其實只有三種可能：要嘛是環、要嘛是鏈、要嘛是孤點。
而什麼樣的連通塊會造成問題呢？很明顯的，只要有奇環，就沒辦法幫邊好好上色了！因此，這題的做法也跟著變得非常乾淨：建完圖後，判斷是否每個點的度數都不超過 $2$，再判斷是否存在奇環就好。
看到這裡，也許讀者會心想：感覺就算我不這樣建圖，我還是可以解完這道題目啊？有需要這樣大費周章嗎？
不過，若我們希望在比賽中求快，除了讓思考變快之外，實作速度也是一大重點。由於上述這個做法寫起來相當簡單，如果能在賽中快速的得到這個結論，其實還是可以大大減少自己的實作時間來取得優勢。因此能熟練掌握建圖的技巧還是相當有用的。
也是有一種類型的題目，即使圖本身已經赤裸裸的擺在題敘裡了，最後解題所使用的圖卻不完全是題目給的圖。
有 $n$ 個城市和 $m$ 條道路，已知有 $k$ 個城市裡面有動漫商店，對於每個城市，請找到他最少要經過幾條道路才能抵達有動漫商店的城市？
如果 $k=1$，那這其實就只是一個單純的最短路徑問題，靠一個 BFS 就能解決。
但如果 $k>1$ 要怎麼辦呢？在概念上，我們其實可以做一個這樣的轉換：我們建一張新的圖，這張圖和原本的圖幾乎一模一樣，但我們多新增一個點 $\phi$，並將 $\phi$ 和所有有動漫商店的點建一條邊。
如此一來神奇的事便發生了：每個點的答案，其實就是從 $\phi$ 走到他的最短距離，再減去 $1$！
這種在原圖上「多新增的點」通常又會被稱作「虛擬節點」，是在解決圖論問題時，一個可以用來更方便做思考的手段，其實相當的常用。
也許有些讀者可以在不使用虛擬節點概念的情況下，自行從 BFS 的邏輯推演出等價的演算法，但這裡想傳達給讀者的是對「虛擬節點」的基本認識，先對他稍微有個印象，在未來他可大有幫助！
我們在最後來看看這道例題：
給你 $n$ 個字串，這 $n$ 個字串被宣稱是照著「最小字典序」排序的，但他用來當作「字典序」的字母順序卻與我們平常熟悉的 a-z 有所不同。
舉例來說，如果給予的字串照順序依序是 bac、aca、aac，那我們可以推測出，這個順序所使用的「字母順序」有可能是 bca，如此一來才會讓 bac 排在最前面，且 aca 還能夠在 aac 前面。
請你還原出一組可能的「字母順序」，或是說明這不可能。
我們先來看看這題要怎麼建圖。
首先，對於任兩個字串 $s, t$，當 $s$ 的「字典序」比 $t$ 小時，我們可以得到一個資訊：我們試圖從兩個字串的開頭同時開始掃，掃到第一個相異的字元時，即代表 $s$ 這個位置的字元必須比 $t$ 這個位置的字元小。
因此，這給了我們一個線索：我們可以把每個字元當成點、把一個「$a$ 必須比 $b$ 小」的資訊當成一條有向邊，如此一來，這個問題就變成了一個拓撲排序問題！
不過，上述演算法的時間複雜度是什麼呢？因為每個字串可能會參加比較過程 $n$ 次，所以是 $O(n \cdot 字串長度總和 + 26)$，雖然可以通過，但實際上這是有改進空間的。
與其暴力讓每一對字串都建一條邊，不如我們只針對相鄰的字串建邊，這是因為，只要相鄰的字串有被保證順序，其實整串序列的順序就能被確定了。因此，整個演算法保證了每個字串只會參與至多兩次比較過程，就成功的把時間複雜度優化到了 $O(字串長度總和)$！
從上述例子我們可以看到：就算是建圖，也可以很聰明的觀察出有些邊是不需要建立的，進而大量減少建圖所需要的時間、或者空間花費。
在本文章，我們了解到了幾個基礎有關建圖的知識。相信讀者能初步的感受到，就算題目不是圖，也有可能得先找出適合對應成圖論物件的元素，再轉換成圖論問題。
這篇文章做為圖論主題的初始章節，也是為了幫讀者們熱熱身，希望讀者能在後續見到更多奇葩的圖論應用時稍微能接受一些。
一間公司裡有 $N$ 個員工，總共有 $M$ 種語言。給定每個員工會說的語言清單。員工之間只要有共通語言就可以溝通，且溝通具有傳遞性（A 與 B 能溝通，B 與 C 能溝通，A 就能與 C 溝通）。
你可以花費 1 元讓某個員工學會某一種語言，請問最少要花多少錢，才能讓所有員工互相溝通？
有 $N$ 個使用者，一開始第 $i$ 位使用者的名稱為 $S_i$，且他希望改名成 $T_i$。
已知系統內不可以同時存在兩個相同的使用者名稱，你需要依序幫這 $N$ 位使用者進行改名，使得在每位使用者都只改了一次名的前提下，整個改名過程可以順利進行，且不會產生一瞬間有兩個人的名稱一樣。
請輸出這能不能辦到。
給定一個長度為 $n$ 的陣列 $a$。如果你站在索引 $i$，你可以往左跳到 $i - a_i$，或往右跳到 $i + a_i$。
請算出對每個位置來說，最少要跳幾步，才能跳到一個與自己 「奇偶性相反」 的數字（例如偶數出發，要跳到奇數；奇數出發，要跳到偶數）。
給定 $N$ 個集合，每個集合可能包含若干個 $1\sim M$ 之間的數字。如果兩個集合有共通的數字，就可以將這兩個集合合併。請問最少需要合併幾次，才能讓數字 $1$ 和數字 $M$ 處在同一個集合中？或是說明這不可能。
給你一張有向圖。你在玩一種「三級跳」遊戲，也就是每次移動都必須連續走過整整 $3$ 條邊，不能停在中間。請問從起點 $S$ 到終點 $T$，最少需要幾次「三級跳」？
在一個 2D 平面上有很多點。遊戲規則是：如果平面上存在三個點，它們剛好可以組成一個「邊平行於 $x$ 軸與 $y$ 軸的矩形」的三個頂點（也就是存在 $(x_1, y_1)$, $(x_1, y_2)$, $(x_2, y_1)$ 這三點），那麼矩形的第四個頂點 $(x_2, y_2)$ 就會自動生成。新生成的點也可以繼續參與生成。請問最後平面上總共會「新增」幾個點？
現在有一個 $n\times m$ 的 01 表格，以及 $k$ 個形如 $(a_i, b_i)$ 的 pair。
你的目標是要把整張表格的每一格都變成 0，對此你可以進行以下操作至多 $k(n + m)$ 次：
01 翻轉。
請判斷是否能達成目標，或是說明這不可能。