GT chromatic number

 #include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

int n;

int m;

vector<vector<int>> graph;

vector<int> coloring;

void DFS(int u) {

// Skip already visited nodes

if(coloring[u] != -1) {

return ;

}

// Store the colours of the adjacent nodes

vector<int> colors;

for(int v : graph[u]) {

if(coloring[v] != -1) {

colors.push_back(coloring[v]);

}

}

int new_color = 0;

sort(colors.begin(), colors.end());

// Find the minimum color which is not used by

// adjacent nodes

for(int i = 0; i < colors.size(); ++i) {

if(colors[i] == new_color) {

new_color++;

}

else if(colors[i] < new_color) {

continue;

}

else {

break;

}

}

// Colour the current node

coloring[u] = new_color;

// Call DFS for all unvisited adjacent nodes

for(int v : graph[u]) {

if(coloring[v] == -1) {

DFS(v);

}

}

}

int FindChromaticNumber() {

coloring = vector<int>(n + 1, -1);

DFS(1);

int chromatic_num = 1;

for(int i = 1; i <= n; ++i) {

chromatic_num = max(chromatic_num, coloring[i] + 1);

}

return chromatic_num;

}

int main() {

cout<<"Enter number of vertices in the graph: ";

cin>>n;

cout<<"Enter number of edges in the graph: ";

cin>>m;

graph = vector<vector<int>>(n + 1);

for(int i = 1; i <= m; ++i) {

cout<<"Enter Edge #"<<i<<": ";

int u, v;

cin>>u>>v;

graph[u].push_back(v);

graph[v].push_back(u);

}

int chromatic_num = FindChromaticNumber();

cout<<"\nChromatic number of given graph is "<<chromatic_num<<endl;

//cout<<"One possible coloring of the graph is as follows: "<<endl;

/* for(int i = 1; i <= n; ++i) {

cout<<coloring[i]<<" ";

}

cout<<endl;*/

}