ZeroJudge 解題筆記：m583. 精靈王國 (Kingdom)

作者：王一哲
日期：2025年5月31日



ZeroJudge 題目連結：m583. 精靈王國 (Kingdom)

解題想法

我用一層 for 迴圈掃過所有的傳送點，如果這個點已經走過就找下一個點，如果還沒有走過就將它歸零；接下來再用一層 while 迴圈，不斷地找傳送到的下一個點 nxt，直到 nxt 等於 0 為止。

Python 程式碼

使用時間約為 0.1 s，記憶體約為 16.3 MB，通過測試。

import sys

for line in sys.stdin:
    k = int(line)  # k 個傳送點
    imax = 0  # 同一個王國中最多的傳送點數量
    arr = [0] + list(map(int, input().split()))  # 傳送點資料，開頭多一個 0，改成 0 代表已走訪
    for i in range(1, k+1):  # 依序走訪傳送點 1 ~ k
        if arr[i] == 0: continue  # 如果 arr[i] 等於 0，找下一個點
        cnt = 0  # 同一個王國中的傳送點數量
        nxt = arr[i]  # 下一個位置
        arr[i] = 0  # 已走訪 arr[i]
        while nxt != 0:  # 繼續執行直到 nxt 等於 0
            cnt += 1  # cnt 加 1
            tmp = arr[nxt]  # 暫存 arr[nxt] 到 tmp
            arr[nxt] = 0  # 已走訪 arr[nxt]
            nxt = tmp  # 更新 nxt
        imax = max(imax, cnt)  # 更新 imax
    print(imax)

C++ 程式碼

使用時間約為 13 ms，記憶體約為 488 kB，通過測試。

#include <cstdio>
using namespace std;

int main() {
    int k;  // k 個傳送點
    while(scanf("%d", &k) != EOF) {
        int imax = 0;  // 同一個王國中最多的傳送點數量
        int arr[k+1] = {0};  // 傳送點資料，開頭多一個 0，改成 0 代表已走訪
        for(int i=1; i<=k; i++) scanf("%d", &arr[i]);
        for(int i=1; i<=k; i++) {  // 依序走訪傳送點 1 ~ k
            if (arr[i] == 0) continue;  // 如果 arr[i] 等於 0，找下一個點
            int cnt = 0, nxt = arr[i];  // 同一個王國中的傳送點數量，下一個位置
            arr[i] = 0;  // 已走訪 arr[i]
            while(nxt != 0) {  // 繼續執行直到 nxt 等於 0
                cnt++;  // cnt 加 1
                int tmp = arr[nxt];  // 暫存 arr[nxt] 到 tmp
                arr[nxt] = 0;  // 已走訪 arr[nxt]
                nxt = tmp;  // 更新 nxt
            }
            if (cnt > imax) imax = cnt;  // 更新 imax
        }
        printf("%d\n", imax);
    }
    return 0;
}