d286 - 00193 - Graph Coloring
題目描述
題目要求找出一個圖中最多能塗成黑色的節點數量，且相鄰的節點不能同時塗成黑色。如果有多組解，則輸出字典序最小的解。
解題思路
這題使用 backtracking (回溯法) 演算法來解決。我們從第一個節點開始，嘗試將其塗成黑色或白色。對於每個節點，我們檢查將其塗成黑色是否會違反相鄰節點不能同時為黑色的約束。如果沒有違反約束，我們就將該節點塗成黑色，並遞迴地處理下一個節點。如果違反了約束，我們就將該節點塗成白色，並遞迴地處理下一個節點。在遞迴過程中，我們記錄下最多黑色節點的數量以及對應的節點編號。為了得到字典序最小的解，在找到相同數量的黑色節點時，不更新答案。
複雜度分析
- 時間複雜度: O(2^n)，其中 n 是節點的數量。因為對於每個節點，我們都有兩種選擇（黑色或白色），所以最壞情況下需要遍歷所有可能的組合。
- 空間複雜度: O(n)，主要用於儲存圖的鄰接矩陣
a、節點顏色r和答案ansp。
程式碼
#include <iostream>
#include <string.h>
using namespace std;
int t,n,m,a[105][105],x,y,r[105],ansp[105],ans;
void dfs(int np,int b){
if(np>n){//dfs stop when np > n and check the answer
((b>ans)&&(memcpy(ansp,r,sizeof(r)))&&(ans=max(ans,b)));
return;
}
if(n-np+b<ans)return;
for(int i=1,bl=1;i<=n&&bl;++i)
if(a[np][i]&&r[i]==1)//check if r[np] can set black
bl=0;
else if(i==n){
r[np]=1;
dfs(np+1,b+1);//set black and dfs next point
}
r[np]=-1;
dfs(np+1,b);//set white and dfs next point
}
int main(){
cin.tie(0); ios::sync_with_stdio(false);
cin >> t;
while(t--){
cin >> n >> m;
ans=0;
for(int i=0;i<=n;++i){
r[i]=ansp[i]=0;
for(int j=0;j<=n;++j)
a[i][j]=0;
}
for(int i=0;i<m;++i){
cin >> x >> y;
a[x][y]=a[y][x]=1;
}
dfs(1,0);
for(int i=1,s=0;i<=n;++i)
if(ansp[i]==1)
(s)?cout << " " << i:cout << ans << "\n" << i,s=1;
cout << "\n";
}
}