solved
I am solving a problem where we have to color a graph with 4 colors such that no adjacent nodes share same colors. I, firstly used a set based approach which wasn't working. Then I used a standard implementation which can be found at: https://www.sanfoundry.com/cpp-program-perform-greedy-coloring/
Here's my code but it is not working as intended:
#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
#define int long long
#define pb push_back
#define all(x) x.begin(), x.end()
const int N = 105;
vector<int> graph[N];
vector<int> color(N);
bool unused[5];
signed main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
int n, m;
cin >> n >> m;
for(int i = 0; i < m; i++){
int x, y;
cin >> x >> y;
graph[x].pb(y);
graph[y].pb(x);
}
color[1] = 1;
for(int i = 2; i<=n; i++){
color[i] = -1;
}
for(int i = 1; i < 4; i++) unused[i] = 0;
for(int i = 2; i <= n; i++){
for(auto child: graph[i]){
if(color[child] != -1) unused[color[child]] = 1;
}
int cr;
for(cr = 1; cr <= 4; cr++){
if(unused[cr]) break;
}
color[i] = cr;
for(auto child: graph[i]){
if(color[child] != -1) unused[color[child]] = 0;
}
}
for(int i = 1; i <= n; i++) cout << color[i];
}
For this input:
5 6
4 1
4 2
4 3
2 5
1 2
1 5
I get the output 11511 but the correct output is 12133.