PAT 圖論題「六度空間」：BFS 計算各節點 6 步可達比例

題目大意

給定無向圖 N 節點 (≤ 10⁴)、M 邊 (≤ 33N)。對每個節點，輸出距離 ≤ 6 的節點數佔總數百分比 (保留小數點後兩位)。

演算法：多源 BFS 限制深度

對每個節點執行 BFS，僅展開至第 6 層。使用「層級標記法」避免額外佇列結構：

• last 記錄當前層最後一個節點
• tail 記錄下一層最後一個節點
• 出隊時若 node == last，層數 +1，last = tail
• 層數達 6 即停止

C 語言完整實作

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

#define MAXN 10010
#define MAXM 330010

int head[MAXN], to[MAXM<<1], nxt[MAXM<<1], ecnt;
int que[MAXN];
bool vis[MAXN];

void add_edge(int u, int v) {
    to[ecnt] = v; nxt[ecnt] = head[u]; head[u] = ecnt++;
}

int bfs(int src, int N) {
    memset(vis, 0, sizeof(bool)*(N+1));
    int front = 0, rear = 0;
    que[rear++] = src;
    vis[src] = true;
    int cnt = 1, level = 0, last = src, tail = src;

    while (front < rear) {
        int u = que[front++];
        for (int e = head[u]; e != -1; e = nxt[e]) {
            int v = to[e];
            if (!vis[v]) {
                vis[v] = true;
                ++cnt;
                que[rear++] = v;
                tail = v;
            }
        }
        if (u == last) {
            ++level;
            if (level == 6) break;
            last = tail;
        }
    }
    return cnt;
}

int main(void) {
    memset(head, -1, sizeof(head));
    int N, M; scanf("%d %d", &N, &M);
    for (int i = 0; i < M; ++i) {
        int u, v; scanf("%d %d", &u, &v);
        add_edge(u, v); add_edge(v, u);
    }
    for (int i = 1; i <= N; ++i) {
        int cnt = bfs(i, N);
        printf("%d: %.2f%%\n", i, cnt * 100.0 / N);
    }
    return 0;
}

關鍵優化點

• 靜態陣列避免頻繁 malloc/free
• 佇列用環狀陣列 (front/rear)，O(1) 入出
• vis 陣列每次 BFS 重置，用 memset 極快
• 層級控制無需額外結構，常數極小

複雜度

• 時間：O(N·(N+M)) 最壞約 10⁴ × 3.4×10⁵ = 3.4×10⁹ 邊緣過大，但實際 6 層截斷後極快
• 空間：O(N+M)

常見 WA 原因

1. 未處理重邊/自環 (題目通常保證無)
2. 百分比格式：%.2f%% 需雙百分號轉義
3. 浮點精度：用 cnt * 100.0 / N 避免整數除法截斷
4. 節點編號從 1 開始，陣列開 N+1

樣例驗證

輸入:
10 9
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10

輸出:
1: 70.00%
2: 80.00%
3: 90.00%
4: 100.00%
5: 100.00%
6: 100.00%
7: 100.00%
8: 90.00%
9: 80.00%
10: 70.00%