展開目錄
有時候，某一些問題的長相可以被轉成一種特殊的「圖」，而某些圖論演算法會設計給只符合這些特性的圖。二分圖就是一個比較簡單，且非常有名的例子。
Definition 1
如果無向圖 $G$ 可以分成兩個互斥的點集 $S$ 與 $T$，使得 $S$ 與 $T$ 內部都不存在兩點有邊連接（即圖 $G$ 的所有邊都連接 $S$ 上的頂點與 $T$ 上的頂點），則稱圖 $G$ 為二分圖。
下面的圖就是一個二分圖，紅色（上面）與藍色（下面）的點分別代表 $S$ 跟 $T$。
假設給我們一張圖，那要如何判斷是不是二分圖呢？一個很合理的想法就是想辦法找到 $S$ 跟 $T$，而我們可以透過「塗色」來做這件事。
習題
二分塗色問題
Unknown
DFS 可以做很多事，除了遍歷之外，還可以順便計算關於每個節點的許多性質。我們讓 $S$ 的點是一個顏色，而 $T$ 的點是另一個顏色。以二分圖來說，我們希望每一個點的顏色和鄰接的頂點不同。為了滿足這個性質，我們可以在走到一個頂點時，都將其周圍的點都塗上與之相反的顏色，直到出現矛盾或者整張塗皆被完全上色。要注意的是輸入的圖不一定是連通圖，所以要對每個連通塊嘗試塗色才行。
cpp
vector<int> adj[40010];
int color[40010];
int isbipartite;
void dfs(int s){
for(auto i: adj[s]){
// 將所有鄰接的點塗上與自己不同的顏色
if(!color[i]) color[i] = -color[s], dfs(i);
// 如果兩個相同顏色點鄰接，則不是二分圖
if(color[i] == color[s]) isbipartite = 0;
}
}
int main(){
int n, m;
while(cin >> n >> m, n){
// 初始化
isbipartite = 1;
for(int i = 1; i <= n; i++){
adj[i].clear(), color[i] = 0;
}
// 輸入
for(int i = 0; i < m; i++){
int from, to;
cin >> from >> to;
adj[from].push_back(to);
adj[to].push_back(from);
}
// dfs （二分圖不一定是連通圖！）
for(int i = 1; i <= n; i++){
if(!color[i]) color[i] = 1, dfs(i);
}
cout << (isbipartite? "Yes": "No") << endl;
}
}
這是建中校內賽的簽到題，有了這題再加八分就有當年的校隊！
習題
分點問題（一）
Source:TIOJ
給一張無向圖，若此圖為二分圖，則輸出此圖分成的兩個部分的頂點數及編號；若不是，則輸出 $-1$。
條件限制
$(|V| \leq 10^6, |E| \leq 2\times 10^6)$
習題
Mahmoud and Ehab and the bipartiteness
Source:Codeforces 862B
給定一棵樹（沒有任何環的連通圖），請問最多可以額外添加幾條邊，使得這張圖仍然是二分圖？注意，添加新的邊之後，仍然必須是簡單圖。
條件限制
- $1 \leq n \leq 10^5$