3-coloring in non-deterministic polynomial time

3-coloring.c

#include <err.h>
#include <errno.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/wait.h>
#include <unistd.h>

enum {
    SOLVED = 0,
    UNSOLVED,
    FAILED
};

enum {
    N = 20
};

static int n, m, G[N][N], color[N];

static void wait_or_fail() {
    int status;
    while (1) {
        if (wait(&status) == -1) {
            if (errno == ECHILD)  {
                /* already waited for all of the children */
                exit(UNSOLVED);
            }
            err(FAILED, "wait failed");
        }
        if (WIFEXITED(status) && WEXITSTATUS(status) == SOLVED) {
            exit(SOLVED);
        }
    }
    /* this function never returns */
    __builtin_unreachable();
}

int main() {
    scanf(" %d %d", &n, &m);
    for (int i = 0, u, v; i < m; i++) {
        scanf(" %d %d", &u, &v);
        G[u][v] = G[v][u] = 1;
    }
    for (int u = 1; u <= n; u++) {
        int ok[3] = {1, 1, 1};
        for (int v = 1; v < u; v++) {
            if (G[u][v]) {
                ok[color[v]] = 0;
            }
        }
        /* I will try the first color, my children try other options */
        color[u] = -1;
        for (int c = 0; c <= 2; c++) {
            if (!ok[c]) {
                continue;
            }
            if (color[u] == -1) {
                color[u] = c;
                if (u <= 2 || u == n) {
                    /* optimization */
                    break;
                }
            } else {
                pid_t pid;
                if ((pid = fork()) == -1) {
                    err(FAILED, "fork failed");
                } else if (pid == 0) {
                    /* I am the child */
                    color[u] = c;
                    break;
                }
            }
        }
        if (color[u] == -1) {
            wait_or_fail();
        }
    }
    printf("SUCCESS: ");
    for (int u = 1; u <= n; u++) {
        printf("%d ", color[u]);
    }
    printf("\n");
    exit(SOLVED);
}