Why is my graph coloring code not coloring the graph correctly?

68 Views Asked by At

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.

0

There are 0 best solutions below