結果
問題 | No.2910 単体ホモロジー入門 |
ユーザー |
|
提出日時 | 2023-11-25 03:19:50 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 40 ms / 2,000 ms |
コード長 | 1,185 bytes |
コンパイル時間 | 442 ms |
コンパイル使用メモリ | 82,180 KB |
実行使用メモリ | 53,964 KB |
最終ジャッジ日時 | 2024-09-26 10:10:52 |
合計ジャッジ時間 | 3,462 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 47 |
ソースコード
# 閉路検出 def find_cycles_with_paths(graph): def dfs(node, path): if visited[node]: # 閉路の開始点に戻った場合 if path and node == path[0]: unique_cycles.add(tuple(sorted(path))) return visited[node] = True path.append(node) for neighbour in graph[node]: if not visited[neighbour] or (neighbour == path[0] and len(path) > 2): dfs(neighbour, path[:]) path.pop() visited[node] = False visited = [False] * len(graph) unique_cycles = set() for node in range(len(graph)): dfs(node, []) return [list(cycle) for cycle in unique_cycles] # input N, M = map(int, input().split()) G = [[] for _ in range(N)] for _ in range(M): A, B = map(int, input().split()) G[A].append(B) G[B].append(A) # v_0,v_1,v_2 V = set(map(int, input().split())) # pre_ans_list = [set(cycle) for cycle in find_cycles_with_paths(G)] # v_0~v_2を取り除いたリスト ans_list = any(cycle != V for cycle in pre_ans_list) # ans_listの長さが0なら答えはNo if not ans_list: ans = 'No' else: ans = 'Yes' print(ans)