結果
問題 | No.1023 Cyclic Tour |
ユーザー |
![]() |
提出日時 | 2020-04-10 22:54:54 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,076 ms / 2,000 ms |
コード長 | 2,004 bytes |
コンパイル時間 | 164 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 311,168 KB |
最終ジャッジ日時 | 2024-09-15 23:17:08 |
合計ジャッジ時間 | 24,850 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge6 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 49 |
ソースコード
import sysinput = sys.stdin.readlinesys.setrecursionlimit(10**6)class UnionFind(object):def __init__(self, n: int):self.nodes = [-1]*ndef find(self, x: int) -> int:if self.nodes[x] < 0:return xelse:self.nodes[x] = self.find(self.nodes[x])return self.nodes[x]def unite(self, x: int, y: int) -> bool:root_x, root_y, nodes = self.find(x), self.find(y), self.nodesif root_x != root_y:if nodes[root_x] > nodes[root_y]:root_x, root_y = root_y, root_xnodes[root_x] += nodes[root_y]nodes[root_y] = root_xreturn root_x != root_ydef scc(N, G, RG):order = []used = [0]*Ngroup = [None]*Ndef dfs(s):used[s] = 1for t in G[s]:if not used[t]:dfs(t)order.append(s)def rdfs(s, col):group[s] = colused[s] = 1for t in RG[s]:if not used[t]:rdfs(t, col)for i in range(N):if not used[i]:dfs(i)used = [0]*Nlabel = 0for s in reversed(order):if not used[s]:rdfs(s, label)label += 1return label, groupif __name__ == '__main__':N, M = map(int, input().split())edges = []uf = UnionFind(N)for u, v, c in (map(int, input().split()) for _ in range(M)):u -= 1v -= 1if c == 1:if not uf.unite(u, v):print('Yes')exit()else:edges.append((u, v))adj = [set() for _ in range(N)]rev = [set() for _ in range(N)]for u, v in edges:par_u, par_v = uf.find(u), uf.find(v)if par_u == par_v:print('Yes')exit()adj[par_u].add(par_v)rev[par_v].add(par_u)labels, _ = scc(N, adj, rev)if labels < N:print('Yes')else:print('No')