#46418: DFS一點小思路
s11131151@nhsh.tp.edu.tw
(cc)
學校
:
臺北市立內湖高級中學
編號 : 221040
來源 : [111.125.132.37]
最後登入時間 ：
2025-07-15 12:42:21
我說比較重點的思路
// 讀取邊的訊息並建構鄰接表
for(int i = 0;i<m;i++){
int a,b;
cin >> a>> b;
//無向圖需要雙向添加
graph[a].push_back(b);
graph[b].push_back(a);
} 雙向很重要因為題目中有特別提到
//檢查是不是二分圖
bool isBipartite = true;
for(int i =0;i< n;i++){
if(colors[i] == -1){
// 顏色0 DFS
if(!dfs(i, 0)){
isBipartite = false;
break; //發現衝突，提前結束
}
}
} 用函式去檢查她我的顏色是只有0 1
//遞迴
bool dfs(int node, int color){
//1. 標記當前節點顏色
colors[node] = color;
// 2. 檢查所有鄰居節點
for(int neighbor : graph[node]){
if(colors[neighbor] == -1) {//未訪問過
if(!dfs(neighbor, 1-color)) //遞迴 給鄰居上相反色
return false;
}
else if(colors[neighbor] == color)// 鄰居已訪問過且顏色衝突
return false;
}
// 檢查完若無衝突
return true;
}
思路大概是這樣DFS就是遞迴加上回朔