#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
using namespace std;
const int MAXX=200;//設定邊界
int map[MAXX][MAXX]; //鄰接矩陣存盤圖
int x[MAXX]; //顏色色號
int sum=1; //方案數量
int n; //頂點個數
int m;//邊的個數
int color_nums=4; //顏色數量
char a[40];//頂點
void createmap() //創建鄰接矩陣
{
int u; //頂點1
int v; //頂點2
memset(map,0,sizeof(map));
for (int i=1;i<=m;i++)
{
cin >> u>>v;
map[u][v]=1;
map[v][u]=1;
}
}
bool OK(int t) //判斷色號是否相同
{
for(int j=1;j<t;j++) //判斷現在擴展點t和前面t-1個頂點有沒有相連的
{
if(map[t][j]) //如果相連
{
if(x[j]==x[t]) //且如果顏色一樣
{
return false; //回傳false，換色號進行嘗試
}
}
}
return true; //如果色號不一樣就是true
}
void backtrack(int t) //回溯、遞推函式
{
if(t>n&&sum==1) //到達葉子節點
{
sum++; //方案個數
cout << "染色方案為"<< endl;
for (int i=1;i<=n;i++)
{
cout << x[i] << " ";
}
}
else
{
for (int i=1;i<=color_nums;i++) //嘗試別的色號
{
x[t]=i; //記錄色號
if(OK(t)) //如果色號沒有重復
{
backtrack(t+1); //向下遞推繼續執行
}
}
}
}
int main()
{
cin >> m>> n;//輸入頂點數 邊數
createmap();
backtrack(1);
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/125676.html
標籤：C++ 語言
上一篇：wxwidgets代碼里里使用printf列印的東西怎么才能看見
下一篇：請問這一步錯在哪里