Segment Trees - Range Minimum Query Application

Hello, today I'll post a implementation of a Segment Tree which fits for Range Minimum Query.

 I've been studying segment trees about a time, and I'm starting to understand them now, this implementation runs in O(N) for construction and O(log(N)) for query and update.

 Another things is that the source code of the post is stored in a Github Gist

Dominoes Arrangement and Domino

Hi, surfing on BRSPOJ again, I've found a problem similar to another one that I already solved in Aizu Online Judge, they are these two: LinkAOJ and LinkSPOJ.

For the AOJ one, the input is a little different, but in it's essence, it's the same, given 'N' pieces of domino blocks   determine if it's possible to use all the pieces to form an whole valid sequence Dominoes. I've found 2 solutions, one using backtrack which runs in O(M + 2^N) with 'M' being the maximum number of values on a side of a piece and 'N' the total number of pieces.

This solution is good, but it's enough to pass through the tough system test of BRSPOJ, so I've turned to a graph solution, which is better, running only with a simple Depth-First-Search plus 2 iterations over the 'M', which runs in O(|V| + |E| + 2*M): These are the both solutions:

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

int a, b, i, j, k, n, ok, teste = 1, mem[7][7];

void rec(int now, int deep) {
    if(deep == n) {
        ok = 1;
        return;
    }
    for(j = 0; j &lt; = 6; j++) {
        int i = j;
        if(mem[now][i]&gt; 0) {
            mem[now][i]--;
            mem[i][now]--;
            rec(i, deep + 1);
            if(ok == 1) return;
            mem[now][i]++;
            mem[i][now]++;
        }
    }
}

int main(void) {
    while(scanf("%d", &amp; n) &amp; &amp; n != 0) {
        memset(mem, 0, sizeof(mem));
        ok = 0;
        for(i = 0; i &lt; n; i++) {
            scanf("%d%d", &amp; a, &amp; b);
            mem[a][b] += 1;
            mem[b][a] += 1;
        }
        for(k = 0; k &lt; = 6; k++) {
            rec(k, 0);
            if(ok == 1) break;
        }
        printf("Teste %d\n%s\n\n", teste++, ok == 1 ? "sim" : "nao");
    }
    return 0;
}

and

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

int a, b, n, ok, teste = 1, mem[7][7], vis[7], ct[7];

void dfs(int x) {
    vis[x] = 1;
    for(int j = 0; j <= 6; j++) {
        if(vis[j] == 0 && mem[x][j] == 1) dfs(j);
    }
}

int main(void) {
    while(scanf("%d", &n) && n != 0) {
        memset(mem, 0, sizeof(mem));
        memset(vis, 0, sizeof(vis));
        memset(ct, 0, sizeof(ct));
        for(int i = 0; i < n; i++) {
            scanf("%d%d", &a, &b);
            ct[a] += 1;
            ct[b] += 1;
            mem[a][b] = 1;
            mem[b][a] = 1;
        }
        for(int i = 0; i <= 6; i++) {
            if(ct[i] > 0) {
                dfs(i);
                break;
            }
        }
        ok = 1;
        for(int i = 0; i <= 6; i++) {
            if(ct[i] > 0 && !vis[i]) {
                ok = 0;
            }
        }
        int o = 0;
        for(int i = 0; i <= 6; i++) {
            if(ct[i] % 2 == 1) o++;
        }
        printf("Teste %d\n%s\n\n", teste++, ok == 1 && (o == 0 || o == 2) ? "sim" : "nao");
    }
    return 0;
}