#include <stdio.h>

#define NUM_NODES 8
#define TOTAL_EDGES 9

// グラフの隣接行列（元データ）
// graph[u][v] は、頂点uから頂点vへの有向辺の数を示します
int base_graph[NUM_NODES][NUM_NODES] = {
    // 0  1  2  3  4  5  6  7  (移動先の頂点)
    { 0, 1, 1, 0, 0, 0, 0, 0 }, // 頂点0から 1, 2 へ
    { 0, 0, 0, 1, 0, 0, 0, 0 }, // 頂点1から 3 へ
    { 0, 0, 0, 0, 1, 0, 0, 0 }, // 頂点2から 4 へ
    { 0, 0, 0, 0, 0, 1, 0, 0 }, // 頂点3から 5 へ
    { 0, 0, 0, 0, 0, 0, 1, 0 }, // 頂点4から 6 へ
    { 0, 0, 0, 0, 0, 0, 0, 1 }, // 頂点5から 7 へ
    { 1, 0, 0, 0, 0, 0, 0, 0 }, // 頂点6から 0 へ
    { 0, 0, 1, 0, 0, 0, 0, 0 }  // 頂点7から 2 へ（巡回を生み出すための辺）
};

int current_graph[NUM_NODES][NUM_NODES];
int path[TOTAL_EDGES + 1]; // 通った頂点の履歴を保存する配列
int route_count = 0;

// 深さ優先探索（DFS）による一筆書き探索関数
void find_eulerian_paths(int current_node, int edge_count) {
    // すべての辺（9本）を通りきったら一筆書き成功
    if (edge_count == TOTAL_EDGES) {
        route_count++;
        printf("ルート %d: ", route_count);
        for (int i = 0; i <= TOTAL_EDGES; i++) {
            printf("%d", path[i]);
            if (i < TOTAL_EDGES) printf(" -> ");
        }
        printf("\n");
        return;
    }

    // 次の移動先となる頂点を探索
    for (int next_node = 0; next_node < NUM_NODES; next_node++) {
        // 現在の頂点から次の頂点へ移動できる辺が残っているか
        if (current_graph[current_node][next_node] > 0) {
            
            // 辺を消費（通過フラグ）
            current_graph[current_node][next_node]--;
            path[edge_count + 1] = next_node;

            // 再帰的に次のステップを探索
            find_eulerian_paths(next_node, edge_count + 1);

            // 状態を元に戻す（バックトラッキング）
            current_graph[current_node][next_node]++;
        }
    }
}

int main(void) {
    printf("グラフのサイズ: 頂点数 %d, 辺の総数 %d\n", NUM_NODES, TOTAL_EDGES);
    printf("--- 一筆書きルートの探索開始 ---\n\n");

    // すべての頂点（0〜7）を始点として試す
    for (int start_node = 0; start_node < NUM_NODES; start_node++) {
        
        // ワーク用のグラフ配列に初期データをコピー
        for (int i = 0; i < NUM_NODES; i++) {
            for (int j = 0; j < NUM_NODES; j++) {
                current_graph[i][j] = base_graph[i][j];
            }
        }

        // 始点をセットして探索開始
        path[0] = start_node;
        find_eulerian_paths(start_node, 0);
    }

    printf("\n発見された一筆書きルートの総数: %d\n", route_count);

    return 0;
}