merge 1-NN graph into connected components.

one_nn_merge.c

#include <stdio.h>
#include <string.h>

static void
_merge(int *labels, int n, int src, int dst) {
    for (int i = 0; i < n; ++i) {
        if (labels[i] == src)
            labels[i] = dst;
    }
}

static void
_setv(int *labels, int n, const int v) {
    switch(v) {
        case 0:
            memset(labels, 0, sizeof(int) * n);
            break;
        default:
            for (int i = 0; i < n; ++i)
                labels[i] = v;
    }
}

void
one_link(const int *arr, int n, int *labels) {
    int id = 0;
    _setv(labels, n, -1);

    for (int i = 0; i < n; ++i) {
        const int nn = arr[i];
        const int cond0 = (labels[i]  == -1);
        const int cond1 = (labels[nn] == -1);

        switch( cond0 + cond1 ) {
            case 2:
                labels[i] = labels[nn] = id++;
                break;
            case 1:
                if (cond0) {
                    labels[i] = labels[nn];
                    break;
                }
                labels[nn] = labels[i];
                break;
            case 0:
                if ( arr[i] != arr[nn]) {
                    _merge(labels, i+1, labels[i], labels[nn]);
                }
                break;
        }
    }
}