結果

問題 No.679 不思議マーケット
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 19:58:27
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 59 ms / 2,000 ms
コード長 1,302 bytes
コンパイル時間 192 ms
コンパイル使用メモリ 82,048 KB
実行使用メモリ 68,480 KB
最終ジャッジ日時 2025-06-12 20:01:23
合計ジャッジ時間 1,829 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque, defaultdict

def main():
    input = sys.stdin.read().split()
    ptr = 0
    n = int(input[ptr])
    ptr += 1
    m = int(input[ptr])
    ptr += 1

    g_i_dict = {}
    for _ in range(m):
        g_i = int(input[ptr])
        ptr += 1
        r_i = int(input[ptr])
        ptr += 1
        h_list = list(map(int, input[ptr:ptr + r_i]))
        ptr += r_i
        g_i_dict[g_i] = h_list.copy()

    all_products = set(range(1, n + 1))
    mandatory_products = all_products - set(g_i_dict.keys())

    edges = defaultdict(list)
    in_degree = defaultdict(int)
    for g in g_i_dict:
        in_degree[g] = 0  # Initialize in_degree for all g_i's

    for g_i in g_i_dict:
        for h in g_i_dict[g_i]:
            if h in g_i_dict:
                edges[h].append(g_i)
                in_degree[g_i] += 1

    queue = deque()
    for g in g_i_dict:
        if in_degree[g] == 0:
            queue.append(g)

    top_order = []
    count = 0

    while queue:
        u = queue.popleft()
        top_order.append(u)
        count += 1
        for v in edges[u]:
            in_degree[v] -= 1
            if in_degree[v] == 0:
                queue.append(v)

    total = len(mandatory_products) + count
    print(total)

if __name__ == "__main__":
    main()
0