ZeroJudge 解題筆記：n689. pD. 技能點數

作者：王一哲
日期：2025年12月11日


ZeroJudge 題目連結：n689. pD. 技能點數

解題想法

我用接鄰矩陣 graph 儲存有向圖，用串列 need 儲存學習各技能所需的前置技能，用集合 learn 儲存學到的技能。將一開始拿到的技能書 book 存入待走訪佇列 que，用 BFS 找出所有可以學到的技能。

Python 程式碼

使用時間約為 29 ms，記憶體約為 4.1 MB，通過測試。

from collections import deque

n, m, k = map(int, input().split())
book = list(map(int, input().split()))
graph = [[] for _ in range(n)]
need = [set() for _ in range(n)]
for _ in range(m):
    u, v = map(int, input().split())
    graph[u].append(v)
    need[v].add(u)
for b in book: need[b].clear()
learn = set(book)
que = deque(book)
while que:
    u = que.popleft()
    for v in graph[u]:
        if u in need[v]:
            need[v].remove(u)
        if not need[v]:
            que.append(v)
            learn.add(v)
print(len(learn))

C++ 程式碼

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

#include <cstdio>
#include <vector>
#include <set>
#include <queue>
using namespace std;

int main() {
    int n, m, k; scanf("%d %d %d", &n, &m, &k);
    vector<int> book (k);
    for(int i=0; i<k; i++) scanf("%d", &book[i]);
    vector<vector<int>> graph (n);
    vector<set<int>> need (n);
    for(int i=0; i<m; i++) {
        int u, v; scanf("%d %d", &u, &v);
        graph[u].push_back(v);
        need[v].insert(u);
    }
    set<int> learn;
    queue<int> que;
    for(int b : book) {
        need[b].clear();
        learn.insert(b);
        que.push(b);
    }
    while(!que.empty()) {
        int u = que.front();
        que.pop();
        for(int v : graph[u]) {
            if (need[v].count(u) == 1) need[v].erase(u);
            if (need[v].empty()) {
                que.push(v);
                learn.insert(v);
            }
        }
    }
    printf("%ld\n", learn.size());
    return 0;
}