/* C11. undirected graph with at most six vertices. */
#include <assert.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdio.h>
#define MAX_V 6

typedef struct { bool edge[MAX_V][MAX_V]; size_t n; } Graph;
static bool add_edge(Graph *g, size_t u, size_t v)
{
    if (g->n > MAX_V || u >= g->n || v >= g->n) return false;
    g->edge[u][v] = true; g->edge[v][u] = true;
    return true;
}
/* Return the count reached, or zero for an invalid start. out has MAX_V slots. */
static size_t bfs(const Graph *g, size_t start, size_t out[])
{
    if (g->n > MAX_V || start >= g->n) return 0;
    bool visited[MAX_V] = {false};
    size_t queue[MAX_V], front = 0, rear = 0, count = 0;
    queue[rear++] = start; visited[start] = true;
    while (front < rear) {
        size_t u = queue[front++]; out[count++] = u;
        for (size_t v = 0; v < g->n; ++v)
            if (g->edge[u][v] && !visited[v]) {
                visited[v] = true; /* Mark when enqueued: no duplicates. */
                queue[rear++] = v;
            }
    }
    return count;
}
static void visit(const Graph *g, size_t u, bool visited[], size_t out[], size_t *n)
{
    visited[u] = true; out[(*n)++] = u;
    for (size_t v = 0; v < g->n; ++v)
        if (g->edge[u][v] && !visited[v]) visit(g, v, visited, out, n);
}
static size_t dfs(const Graph *g, size_t start, size_t out[])
{
    if (g->n > MAX_V || start >= g->n) return 0;
    bool visited[MAX_V] = {false}; size_t n = 0;
    visit(g, start, visited, out, &n); return n;
}
static void show(const char *label, const size_t out[], const size_t expected[], size_t n)
{
    printf("%s:", label);
    for (size_t i = 0; i < n; ++i) { assert(out[i] == expected[i]); printf(" %zu", out[i]); }
    putchar('\n');
}
int main(void)
{
    Graph g = {{{false}}, 6}; size_t out[MAX_V];
    assert(add_edge(&g, 0, 1)); assert(add_edge(&g, 0, 2));
    assert(add_edge(&g, 1, 3)); assert(add_edge(&g, 2, 3));
    assert(add_edge(&g, 2, 4)); assert(add_edge(&g, 2, 2)); /* self-loop */
    assert(!add_edge(&g, 0, 6));
    const size_t b[] = {0, 1, 2, 3, 4}, d[] = {0, 1, 3, 2, 4};
    size_t n = bfs(&g, 0, out); assert(n == 5); show("BFS", out, b, n);
    n = dfs(&g, 0, out); assert(n == 5); show("DFS", out, d, n);
    assert(bfs(&g, 5, out) == 1 && out[0] == 5); /* disconnected vertex */
    assert(dfs(&g, 5, out) == 1 && out[0] == 5);
    assert(bfs(&g, 6, out) == 0 && dfs(&g, 6, out) == 0);
    g.n = 0; assert(bfs(&g, 0, out) == 0 && dfs(&g, 0, out) == 0);
    puts("graph tests passed");
    return 0;
}