結果

問題 No.2780 The Bottle Imp
ユーザー lydialitvyak
提出日時 2024-06-09 10:28:20
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
RE  
実行時間 -
コード長 2,570 bytes
コンパイル時間 208 ms
コンパイル使用メモリ 12,800 KB
実行使用メモリ 93,064 KB
最終ジャッジ日時 2024-12-29 17:59:28
合計ジャッジ時間 8,989 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 14 WA * 2 RE * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import defaultdict


def parse_input():
    import sys

    input = sys.stdin.read
    lines = input().strip().split("\n")
    N = int(lines[0].strip())
    connections = []
    for i in range(1, N + 1):
        parts = list(map(int, lines[i].strip().split()))
        M_i = parts[0]
        A_i = parts[1:]
        connections.append(A_i)
    return N, connections


def build_graph(N, connections):
    graph = defaultdict(list)
    for i in range(N):
        for person in connections[i]:
            graph[i + 1].append(person)
    return graph


def tarjan_scc(N, graph):
    index = 0
    stack = []
    indices = [-1] * (N + 1)
    lowlinks = [-1] * (N + 1)
    on_stack = [False] * (N + 1)
    sccs = []

    def strongconnect(v):
        nonlocal index
        indices[v] = lowlinks[v] = index
        index += 1
        stack.append(v)
        on_stack[v] = True

        for w in graph[v]:
            if indices[w] == -1:
                strongconnect(w)
                lowlinks[v] = min(lowlinks[v], lowlinks[w])
            elif on_stack[w]:
                lowlinks[v] = min(lowlinks[v], indices[w])

        if lowlinks[v] == indices[v]:
            scc = []
            while True:
                w = stack.pop()
                on_stack[w] = False
                scc.append(w)
                if w == v:
                    break
            sccs.append(scc)

    for v in range(1, N + 1):
        if indices[v] == -1:
            strongconnect(v)

    return sccs


def can_pass_to_all(N, sccs, graph):
    scc_map = {}
    for i, scc in enumerate(sccs):
        for node in scc:
            scc_map[node] = i

    dag = defaultdict(set)
    for v in range(1, N + 1):
        for w in graph[v]:
            if scc_map[v] != scc_map[w]:
                dag[scc_map[v]].add(scc_map[w])

    in_degree = {i: 0 for i in range(len(sccs))}
    for u in dag:
        for v in dag[u]:
            in_degree[v] += 1

    start_scc = scc_map[1]
    if in_degree[start_scc] != 0:
        return "No"

    visited = set()
    stack = [start_scc]

    while stack:
        node = stack.pop()
        if node not in visited:
            visited.add(node)
            for neighbour in dag[node]:
                stack.append(neighbour)

    if len(visited) == len(sccs):
        return "Yes"
    else:
        return "No"


def main():
    N, connections = parse_input()
    graph = build_graph(N, connections)
    sccs = tarjan_scc(N, graph)
    result = can_pass_to_all(N, sccs, graph)
    print(result)


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