编写一个C++代码图着色问题是一个著名的NP完全问题。给定无向图G=VE问可否用K种颜色为V中的每一个顶点分配一种颜色使得不会有两个相邻顶点具有同一种颜色？但本题并不是要你解决这个着色问题而是对给定的一种颜色分配请你判断这是否是图着色问题的一个解。输入格式：输入在第一行给出3个整数V0V≤500、E≥0和K0K≤V分别是无向图的顶点数、边数、以及颜色数。顶点和颜色都从1到V编号。随后E行每行给出一

#include #include using namespace std;

bool isNeighbor(int v1, int v2, vector<vector>& graph) { for (int i = 0; i < graph[v1].size(); i++) { if (graph[v1][i] == v2) { return true; } } return false; }

bool isValidColoring(vector& colors, vector<vector>& graph) { for (int i = 0; i < graph.size(); i++) { for (int j = 0; j < graph[i].size(); j++) { if (colors[i] == colors[graph[i][j]]) { return false; } } } return true; }

int main() { int V, E, K; cin >> V >> E >> K;

vector<vector<int>> graph(V);
for (int i = 0; i < E; i++) {
    int v1, v2;
    cin >> v1 >> v2;
    graph[v1-1].push_back(v2-1);
    graph[v2-1].push_back(v1-1);
}

int N;
cin >> N;

for (int i = 0; i < N; i++) {
    vector<int> colors(V);
    for (int j = 0; j < V; j++) {
        cin >> colors[j];
    }
    
    if (isValidColoring(colors, graph)) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
}

return 0;