//Ex8_1 图着色问题 #include<iostream> #include<vector> using namespace std; const int MAX = 100; struct Node{ int color; vector<int> link; bool visited = false; }node[MAX]; int nf_color = 3, nf_node = 5; void print(){ cout << "着色方案："; for (int i = 1; i <= nf_node; i++) cout << (i ? " " : "") << node[i].color; cout << endl; } bool judge(const int& i, const int& color) { for (auto& it : node[i].link) if (node[it].color == color) return false; return true; } void dfs(int i) { for (int j = 1; j <= nf_color; j++) { if (judge(i,j)) { node[i].color = j; if (i == nf_node) print(); else dfs(i + 1); node[i].color = 0; } } } int main() { node[1].link.assign({2,4,5}); node[2].link.assign({1,3,5}); node[3].link.assign({2,4}); node[4].link.assign({1,3,5}); node[5].link.assign({1,2,4}); dfs(1); return 0; }
