題目出自ITSA競賽，解答僅供參考

題目連結: 樂活單車遊

解答:

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

bool search(int **map, int p, int currentCount, int count, int current, int end);

int main(void)
{
    int n = 0;
    int p = 0;
    int a = 0;
    int b = 0;

    scanf("%d", &n);

    while (n > 0)
    {
        scanf("%d %d %d", &p, &a, &b);

        //初始化陣列
        int **map = new int *[p];
        for (int i = 0; i < p; i++)
        {
            map[i] = new int[p];
            for (int j = 0; j < p; j++)
            {
                map[i][j] = 0;
            }
        }

        int count = 0;
        int r = 0;
        int s = 0;

        while (true)
        {
            scanf("%d", &r);
            if (r == -1)
            {
                break;
            }
            scanf("%d", &s);
            map[r][s] = map[s][r] = 1;
            count++;
        }

        if (search(map, p, 0, count, a, b))
        {
            printf("YES\n");
        }
        else
        {
            printf("NO\n");
        }

        n--;

        //釋放陣列
        for (int i = 0; i < p; i++)
        {
            delete[] map[i];
        }
        delete[] map;
    }

    system("pause");
    return 0;
}

//return       找到路線回傳true
//map          路線地圖
//p            路口數
//currentCount 目前走完的路線數
//count        總路線數
//current      當前路口
//end          終點路口
bool search(int **map, int p, int currentCount, int count, int current, int end)
{
    //成功走完所有路線回到終點
    if (current == end && currentCount == count)
    {
        return true;
    }
    //走完所有路線但沒有回到終點
    if (currentCount == count)
    {
        return false;
    }
    //往下一個路口
    for (int i = 0; i < p; i++)
    {
        if (map[current][i] == 1)
        {
            //將走過的路線移除
            map[current][i] = map[i][current] = 0;

            if (search(map, p, currentCount + 1, count, i, end))
            {
                //找到路線直接返回
                return true;
            }

            //還原移除的路線
            map[current][i] = map[i][current] = 1;
        }
    }
    return false;
}

說明:
路線圖我使用二維陣列 map 儲存，如下圖:
map[a][b] = 1 代表 a 和 b 兩路口相通，
map[a][b] = 0 代表 a 和 b 兩路口不相通。

search 函數做圖形的走訪，這裡我使用深度搜尋，走法如下圖:
假設起點為2
2 -> 1
1 -> 0
0 -> 4
4 -> 1
這時發現沒有路可以走了，原路返回到1，發現可以走4
1 -> 4
4 -> 0
0 -> 1
這時發現沒有路可以走了，原路返回到1，因為 0,4 都已經走過，再繼續返回到2
2 -> 3
PS.因箭頭過多，所以省略中間部分 XD

if (current == end && currentCount == count)
{
    return true;
}

如果當前的路口在終點且所有路線都走完，表示成功找到解答。

if (currentCount == count)
{
    return false;
}

如果所有路線都走完但沒有回到終點，表示此種走法不是解答，返回後繼續搜尋。

if (map[current][i] == 1)

找下一個可以走的路線。

map[current][i] = map[i][current] = 0;
...
map[current][i] = map[i][current] = 1;

這裡做了一個設計，只需將走過的兩個路口設為不相通，就可以確保此路線不會被重複走過，此圖形的路線為雙向的，所以 a,b 和 b,a 都要設定，最後結束時要把路線還原，供下一次走訪使用。

if (search(map, p, currentCount + 1, count, i, end))
{
    return true;
}

題目不需要找出所有解，所以只要找到一個解就直接返回。

結語:
此題還蠻好玩的，需要一點圖形走訪的概念，本來想用堆疊來完成，但 include 找不到 stack 後來就放棄用遞迴。