結果
問題 |
No.679 不思議マーケット
|
ユーザー |
![]() |
提出日時 | 2025-06-12 20:08:19 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,449 bytes |
コンパイル時間 | 746 ms |
コンパイル使用メモリ | 82,516 KB |
実行使用メモリ | 68,828 KB |
最終ジャッジ日時 | 2025-06-12 20:14:37 |
合計ジャッジ時間 | 2,047 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 5 WA * 13 |
ソースコード
import sys from sys import stdin sys.setrecursionlimit(1 << 25) def main(): n, m = map(int, stdin.readline().split()) gi_info = {} non_gi = set(range(1, n+1)) for _ in range(m): parts = stdin.readline().split() g_i = int(parts[0]) r_i = int(parts[1]) h_list = list(map(int, stdin.readline().split())) gi_info[g_i] = h_list non_gi.discard(g_i) subset_S = [] for g in gi_info: has_non_gi_h = False for h in gi_info[g]: if h in non_gi: has_non_gi_h = True break if not has_non_gi_h: subset_S.append(g) graph = {} for g in subset_S: graph[g] = [] for h in gi_info[g]: graph[g].append(h) visited = {} on_stack = {} has_cycle = False def dfs(node): nonlocal has_cycle if node in on_stack: has_cycle = True return if node in visited: return visited[node] = True on_stack[node] = True for neighbor in graph.get(node, []): if neighbor in subset_S: dfs(neighbor) on_stack.pop(node, None) for node in subset_S: if node not in visited: dfs(node) if has_cycle: break if has_cycle: print(5) else: print(n) if __name__ == "__main__": main()