# [graph coloring problem] detailed optimization

## Graph coloring problem

### 

Given undirected connected graphs, G and m have different colors. These colors are used to color the vertices of graph G, and each vertex has a color. Is there a shading method that makes the 2 vertices of each edge in G have different colors.

### 

If a graph needs at least m colors to make the two vertices connected by each edge in the graph have different colors, this number m is called the chromatic number of the graph.

## Problem solving ideas

#### problem analysis

The first is to give a picture and a fixed color, so that we can judge whether we can dye successfully or have several dyeing schemes;

#### Problem solving ideas

Backtracking + DFS

• The i-th node is dyed with dfs(i). When I > N, the dyeing is completed;
• For each node, it is necessary to enumerate all nodes connected to it to see whether the colors coincide. If the colors coincide, enumerate the next color. If a color does not coincide with the connected node, enumerate the next node (dfs(i+1));
• After all colors are enumerated, if there are still no qualified ones, go back and enumerate again;
• If you find it, you don't need to go back, because you only need to judge whether the dyeing can be successful (this should be paid special attention);

#### Code demonstration

```#include<iostream>
#include<cstring>
using namespace std;
const int maxn = 110;
int G[maxn][maxn];
int color[maxn];
bool ans;
int n,m,k;
void init(){
//Used for array initialization
ans = 0;
memset(G, 0 , sizeof G);
memset(color, 0 , sizeof color);
}

void dfs(int cur){
if(cur > n) {
ans = 1;
return;
}
for(int i=1; i<=m; i++){
//Try to paint cur nodes with each color

bool flag = 1;
//Nodes before cur must be colored
for(int j=1; j<cur; j++){
if(G[j][cur] == 1 && color[j] == i){
flag = 0;
//Not as long as there is a conflict
break;
}
}
//If i color can be painted, consider the next node
if(flag){
color[cur] = i;
dfs(cur + 1);
//color[curr]=0;
//!!! When you need to find the number of schemes, backtracking should be put here to find all schemes!!!;
}
//If the cur node cannot be colored at this step, return to explore other schemes
else color[cur] = 0;
//to flash back;
}

}

int main(){
while(cin>>n>>k>>m){
init();
for(int i=1; i<=k; i++){
int x,y;
cin>>x>>y;
G[x][y] = G[y][x] = 1;
}
dfs(1);
cout<<ans<<endl;
}
return 0;
}
```

### Topic exercise

#### problem analysis

Given a graph, let's find out the minimum number of colors needed for complete coloring;

#### Problem solving ideas

Use backtracking to find out all schemes and record the number of colors;

#### Code demonstration

```#include<bits/stdc++.h>
using namespace std;
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<3)+(x<<1)+(ch^48);
ch=getchar();
}
return x*f;
}
/*
vector<int>Room[M]People in the room
Traverse before selecting a room each time, which is similar to the coloring problem
GIndicates the relationship between people
dfs(i,j)
Indicates that the number of rooms i need to live in is j;
*/
int G;
int n;
int ans;
vector<int>Room;
void dfs(int x,int y){
if(y>=ans)return;
//prune
if(x>n){
ans=min(ans,y);
//	cout<<"y "<<y<<endl;
return;
}
for(int j=1;j<=y;j++){
bool flag=1;
//Judge whether this room x can live
for(int i=0;i<Room[j].size();i++){
if(G[Room[j][i]][x]){
flag=0;
break;
}
}
if(flag){
//This room is available
Room[j].push_back(x);
dfs(x+1,y);
Room[j].pop_back();
}
}
//Open another room for x
Room[y+1].push_back(x);
dfs(x+1,y+1);
Room[y+1].pop_back();

}
void init(){
memset(Room ,  0, sizeof Room);
memset(G,  0, sizeof G);
ans = INT_MAX;
}
int main(){
init();
int m,a,b;
while(m--){