C++ программа, которая по списку названий городов находит все наиболее длинные цепочки, которые можно из этого списка составить.

[UrfinJuicy]

Задача:

Игра в «Города» заключается в следующем. Несколько игроков по очереди говорят название города. Начальная буква каждого следующего названия должна совпадать с последней буквой предыдущего. Никакой город не может быть назван дважды.

Требуется написать программу, которая по списку названий городов находит все наиболее длинные цепочки, которые можно из этого списка составить.

На стандартном потоке ввода задаётся сначала число N (0 ≤ N ≤ 10) — количество городов. В последующих N строках записаны название городов. Каждое из названий не превышает 20 символов и состоит из заглавных латинских букв. Названия городов могут повторяться, в этом случае города считаются различными и могут использоваться в цепочке столько раз, сколько раз они встречаются в списке. Кроме того, цепочки начинающиеся с каждого из них, считаются различными.

На стандартный поток вывода требуется сначала вывести число K — длину максимально возможной цепочки. В последующих строках необходимо вывести названия всех городов, с которых могут начинаться цепочки длины K. Города в выводе не должны повторяться. Выводите города в том же порядке, в котором они встречались во входном файле.

___________________________________ ______________

Идея: заносим города в ориентированный граф и делаем DFS из каждой вершины, смотрим на глубину...
Вот моя реализация, но такое решение падает, не подскажете где ошибка?

//
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <float.h>
#include <ctype.h>
#include <string.h>

// _______________________________________________________________________

struct city {
    char begin, end, word[30];
    int size;
};
typedef struct city city;

void fill(int *a, int size, int val) {
    for (int i = 0; i < size; ++i) a[i] = val;
}

int n, ans = 0;
int ans_list[11];


void dfs(int g[n + 1][n + 1], int used[n+1], int u, int level, int start) {
    ++level;
    int flag = 0;
    used[u] = 1;
    for (int i = 1; i <= n; ++i) {
        if (g[u][i] && !used[i]) {
            flag = 1;
            dfs(g, used, i, level, start);
        }
    }
    if (!flag) {
        if (level == ans) {
            ans_list[start] = 1;
        } else if (level > ans) {
            ans = level;
            fill(ans_list, n+1, 0);
            ans_list[start] = 1;
        }
    }
}


int main(void) {

    fill(ans_list, n+1, 0);
    scanf("%d", &n);
    city * list = (city *)malloc((n + 1) * sizeof(city));
    for (int i = 1; i <= n; ++i) {
        scanf("%s", list[i].word);
        list[i].size = strlen(list[i].word);
        list[i].begin = list[i].word[0];
        list[i].end = list[i].word[list[i].size-1];
    }
    int g[n+1][n+1];
    for (int i = 1; i <= n; ++i)
        fill(g[i], n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (j == i) continue;
            if (list[i].end == list[j].begin) g[i][j] = 1;
        }
    }
    for (int i = 1; i <= n; ++i) {
        int used[n+1];
        fill(used, n+1, 0);
        dfs(g, used, i, 0, i);
    }
    printf("%d\n", ans);
    for (int i = 1; i <= n; ++i) {
        if (ans_list[i])
            printf("%s\n", list[i].word);
    }
    free(list);
    
    return 0;
}

// _______________________________________________________________________

[FPaul]

Мне почему-то кажется, что требуется найти радиус графа, а он ищется через алгоритм Дейкстры или Флойда-Уоршалла - точно не помню.