結果

問題 No.679 不思議マーケット
コンテスト
ユーザー lam6er
提出日時 2025-04-09 21:00:55
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,890 bytes
コンパイル時間 174 ms
コンパイル使用メモリ 82,344 KB
実行使用メモリ 71,976 KB
最終ジャッジ日時 2025-04-09 21:01:43
合計ジャッジ時間 2,090 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 7 WA * 11
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
from collections import defaultdict

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

    conditions = []
    conditional_g_set = set()

    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
        conditions.append((g_i, r_i, h_list))
        conditional_g_set.add(g_i)

    if m == 0:
        print(n)
        return

    # Build the dependency graph among conditional goods
    graph = defaultdict(list)
    nodes = list(conditional_g_set)
    for g_i, r_i, h_list in conditions:
        for h in h_list:
            if h in conditional_g_set:
                graph[g_i].append(h)

    # Implement Tarjan's algorithm for SCC
    index = 0
    indices = {}
    low = {}
    on_stack = set()
    stack = []
    sccs = []

    def strongconnect(v):
        nonlocal index
        indices[v] = index
        low[v] = index
        index += 1
        stack.append(v)
        on_stack.add(v)
        for w in graph[v]:
            if w not in indices:
                strongconnect(w)
                low[v] = min(low[v], low[w])
            elif w in on_stack:
                low[v] = min(low[v], indices[w])
        if low[v] == indices[v]:
            scc = []
            while True:
                w = stack.pop()
                on_stack.remove(w)
                scc.append(w)
                if w == v:
                    break
            sccs.append(scc)

    for v in nodes:
        if v not in indices:
            strongconnect(v)

    invalid_count = 0
    for scc in sccs:
        if len(scc) >= 2:
            invalid_count += len(scc)

    print(n - invalid_count)

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