AtCoder真題及詳細題解 ABC427C： Bipartize
題目描述
有一個簡單的無向圖，包含 
你將執行零次或多次以下操作：
- 選擇一條尚未被刪除的邊，並將其刪除。
你的目標是使圖變為二分圖。找出使操作後的圖變為二分圖所需的最少操作次數。
簡單圖是什麼意思？
簡單圖當且僅當沒有自環（滿足 
什麼是二分圖？
二分圖是一種圖，其中可以為每個頂點塗上黑色或白色，滿足以下條件：
- 對於每條邊，該邊連接的兩個頂點顏色不同。
輸入格式
輸入從標準輸入按以下格式給出：
輸出格式
輸出使圖變為二分圖所需執行的操作次數。
輸入輸出樣例 #1
輸入 #1
5 8
1 2
1 3
1 4
2 3
2 5
3 4
3 5
4 5輸出 1
2輸入輸出樣例 2
輸入 2
2 1
1 2輸出 2
0輸入輸出樣例 3
輸入 3
10 20
5 9
1 4
3 8
1 6
4 10
5 7
5 6
3 7
3 6
5 10
1 3
3 4
6 7
1 2
4 7
1 5
1 9
9 10
4 5
8 9輸出 3
5説明/提示
樣例解釋 1
你可以通過刪除兩條邊使圖變為二分圖：例如，刪除連接頂點 
通過一次或更少的操作無法使圖變為二分圖，因此輸出 2。
樣例解釋 2
圖從一開始就是二分圖。因此，需要執行的操作次數為 
約束條件
- 給定的圖是簡單圖。
- 所有輸入值都是整數。
AC代碼
#include<bits/stdc++.h>
using namespace std;
int n, m, t, color[11], ans = 100; // color數組記錄每個頂點的顏色(0或1)，ans記錄最小操作次數
struct node {
int u, v; // 存儲邊的結構體
} a[110]; // 存儲所有邊的數組
// 深度優先搜索函數，i表示當前正在處理的頂點編號
void dfs(int i) {
// 如果所有頂點都已處理完畢
if (i == n + 1) {
int cnt = 0; // 統計需要刪除的邊數
// 遍歷所有邊
for (int j = 1; j <= m; j++) {
// 如果邊的兩個端點顏色相同，説明這條邊需要刪除
if (color[a[j].u] == color[a[j].v]) {
cnt++;
}
}
// 更新最小操作次數
ans = min(ans, cnt);
return;
}
// 嘗試將當前頂點染成顏色0，然後處理下一個頂點
color[i] = 0;
dfs(i + 1);
// 嘗試將當前頂點染成顏色1，然後處理下一個頂點
color[i] = 1;
dfs(i + 1);
}
int main() {
cin >> n >> m;
// 讀入所有邊
for (int i = 1; i <= m; i++) {
cin >> a[i].u >> a[i].v;
}
// 從頂點1開始深度優先搜索
dfs(1);
// 輸出最小操作次數
cout << ans;
return 0;
}算法思路
這是一個使用暴力搜索解決二分圖判定問題的方案。由於題目中N的最大值為10，可以枚舉所有可能的頂點着色方案。
核心思想
- 二分圖的定義：可以用兩種顏色給所有頂點着色，使得任意一條邊的兩個端點顏色不同
- 對於每個頂點，都有兩種可能的顏色選擇（0或1）
- 通過DFS枚舉所有可能的着色方案
- 對於每種着色方案，統計違反二分圖條件的邊數（即兩端點顏色相同的邊數）
- 取所有方案中的最小違規邊數作為答案
關鍵步驟
- DFS枚舉：遞歸地為每個頂點嘗試兩種顏色
- 邊界條件：當處理完所有頂點後，評估當前着色方案
- 邊檢查：對於每條邊，檢查兩個端點顏色是否相同
- 結果更新：記錄所有方案中的最小違規邊數
複雜度分析
- 時間複雜度：O(
- 空間複雜度：O(N + M)，用於存儲顏色數組和邊列表
#include<bits/stdc++.h>
using namespace std;
int main(){
cout<本文章為轉載內容，我們尊重原作者對文章享有的著作權。如有內容錯誤或侵權問題，歡迎原作者聯繫我們進行內容更正或刪除文章。