結果
問題 |
No.2780 The Bottle Imp
|
ユーザー |
![]() |
提出日時 | 2024-06-18 00:53:02 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 524 ms / 2,000 ms |
コード長 | 2,355 bytes |
コンパイル時間 | 347 ms |
コンパイル使用メモリ | 81,904 KB |
実行使用メモリ | 150,016 KB |
最終ジャッジ日時 | 2024-06-18 00:53:15 |
合計ジャッジ時間 | 10,855 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 40 |
ソースコード
class SCCGraph: def __init__(self, G): self.N = N = len(G) self.G = G self.H = [[] for _ in range(N)] for v in range(N): for a in G[v]: self.H[a].append(v) called = [False]*N closed = [False]*N preO = [] postO = [] def dfs(s): Q = [~s, s] while Q: v = Q.pop() if v >= 0: if called[v]: continue called[v] = True preO.append(v) for a in reversed(self.G[v]): if called[a]: continue Q.append(~a) Q.append(a) else: v = ~v if closed[v]: continue closed[v] = True postO.append(v) for s in range(N): if called[s]: continue dfs(s) found = [False]*N self.SCCs = SCCs = [] self.atlas = atlas = [-1]*N cur = 0 for s in reversed(postO): if found[s]: continue SCC = [] Q = [s] while Q: v = Q.pop() if found[v]: continue found[v] = True SCC.append(v) for a in self.H[v]: Q.append(a) SCCs.append(SCC) for v in SCC: atlas[v] = cur cur += 1 SCCs.reverse() for v in range(N): atlas[v] = cur-1-atlas[v] self.DAG: list|None = None def contract(self): dag = [set() for _ in range(len(self.SCCs))] for v in range(self.N): for a in self.G[v]: if self.atlas[v] == self.atlas[a]: continue dag[self.atlas[v]].add(self.atlas[a]) return [list(d) for d in dag] INF = float("INF") N = int(input()) G = [[] for _ in range(N)] for v in range(N): M, *A = map(int, input().split()) G[v] = [a-1 for a in A] sccG = SCCGraph(G) nG = sccG.contract() ns = sccG.atlas[0] nN = len(nG) found = [False]*nN Q = [ns] found[ns] = True while True: v = Q.pop() for a in nG[v]: if found[a]: continue else: Q.append(a) found[a] = True break else: break ans = all(found) if ans is True: print("Yes") else: print("No")