图着色问题C++实现

以下是一个使用C++实现图着色问题的示例代码：

#include <iostream>
#include <list>
#include <vector>

using namespace std;

class Graph {
    int V;
    list<int> *adj;

public:
    Graph(int V) {
        this->V = V;
        adj = new list<int>[V];
    }

    void addEdge(int v, int w) {
        adj[v].push_back(w);
        adj[w].push_back(v);
    }

    bool isSafe(int v, vector<int>& color, int c) {
        for (auto it = adj[v].begin(); it != adj[v].end(); ++it) {
            if (color[*it] == c) {
                return false;
            }
        }
        return true;
    }

    bool graphColoringUtil(vector<int>& color, int m, int v) {
        if (v == V) {
            return true;
        }

        for (int c = 1; c <= m; c++) {
            if (isSafe(v, color, c)) {
                color[v] = c;
                if (graphColoringUtil(color, m, v + 1)) {
                    return true;
                }
                color[v] = 0;
            }
        }

        return false;
    }

    bool graphColoring(int m) {
        vector<int> color(V, 0);
        if (graphColoringUtil(color, m, 0)) {
            cout << "Graph can be colored with at most " << m << " colors." << endl;
            cout << "Coloring scheme: ";
            for (int i = 0; i < V; i++) {
                cout << color[i] << " ";
            }
            cout << endl;
            return true;
        } else {
            cout << "Graph cannot be colored with " << m << " colors." << endl;
            return false;
        }
    }
};

int main() {
    int V, E, m;
    cout << "Enter the number of vertices in the graph: ";
    cin >> V;
    cout << "Enter the number of edges in the graph: ";
    cin >> E;

    Graph g(V);

    cout << "Enter the edges (vertex pairs):" << endl;
    for (int i = 0; i < E; i++) {
        int v, w;
        cin >> v >> w;
        g.addEdge(v, w);
    }

    cout << "Enter the maximum number of colors: ";
    cin >> m;

    g.graphColoring(m);

    return 0;
}