Zerojudge. k734 開啟寶盒

題解

這是topological的題目。先記錄好每一個寶盒需要多少鑰匙，每當寶盒開啟，就把它有的鑰匙對應的寶盒的需要鑰匙數-1，並把對應寶盒加進去stack

Python 解答

from sys import stdin
# 輸入測資
n, m, k = map(int, stdin.readline().split())

# 持有的鑰匙(記得把第一個數字去除)
keys = list(map(int, stdin.readline().split()))[1:]

needs = [k] * n   # 第index個寶箱還需要的鑰匙數量
gets = []         # 開啟第index個寶箱拿到的鑰匙

# 開啟第index個寶箱需要的鑰匙
opens = [[] for _ in range(n)]

have = [False] * m # 判斷是否擁有此鑰匙
# 先將拿到的鑰匙去除
for _ in keys : have[_] = True

for _ in range(n) :
    # 輸入測資
    for i in list(map(int, stdin.readline().split())) :
        opens[i].append(_)

for _ in range(n) :
    # 輸入測資
    get = list(map(int, stdin.readline().split()))
    gets.append(get)

ans = 0
while keys :
    key = keys.pop() # 現在的鑰匙

    # 跑過所有key能開的寶箱
    for _ in opens[key] :
        needs[_] -= 1   # 寶箱_所需鑰匙數-1
        
        if needs[_] == 0 : # 寶箱開啟
            ans += 1 
            for nk in gets[_] : # 跑過得到的鑰匙
                if not have[nk] : # 如果nk鑰匙是沒拿過的
                    have[nk] = True 
                    keys.append(nk) # 新增nk到持有的鑰匙
print(ans)