Untitled

mail@pastecode.io avatar
unknown
plain_text
7 months ago
1.3 kB
1
Indexable
Never
#include <iostream>
#include <vector>
#include <set>
#include <map>

using namespace std;

class Graph {
public:
    Graph(int V);
    void addEdge(int v, int w);
    void colorGraph();

private:
    int V;
    vector<set<int>> adj;
    map<int, int> colorMap;
    
    int getAvailableColor(int v);
};

Graph::Graph(int V) {
    this->V = V;
    adj.resize(V);
}

void Graph::addEdge(int v, int w) {
    adj[v].insert(w);
    adj[w].insert(v);
}

int Graph::getAvailableColor(int v) {
    set<int> usedColors;
    for (const int neighbor : adj[v]) {
        if (colorMap.find(neighbor) != colorMap.end()) {
            usedColors.insert(colorMap[neighbor]);
        }
    }

    int color = 0;
    while (usedColors.count(color)) {
        color++;
    }
    return color;
}

void Graph::colorGraph() {
    for (int v = 0; v < V; v++) {
        colorMap[v] = getAvailableColor(v);
    }

    // Print the coloring
    for (int v = 0; v < V; v++) {
        cout << "Vertex " << v << " is colored with color " << colorMap[v] << endl;
    }
}

int main() {
    int V = 6; // Number of vertices
    Graph graph(V);

    graph.addEdge(0, 1);
    graph.addEdge(0, 2);
    graph.addEdge(1, 3);
    graph.addEdge(2, 4);
    graph.addEdge(3, 5);

    graph.colorGraph();

    return 0;
}