結果
問題 | No.1023 Cyclic Tour |
ユーザー |
![]() |
提出日時 | 2020-04-10 22:01:37 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 468 ms / 2,000 ms |
コード長 | 2,125 bytes |
コンパイル時間 | 304 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 137,628 KB |
最終ジャッジ日時 | 2024-09-15 20:21:30 |
合計ジャッジ時間 | 18,814 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 49 |
ソースコード
def main():import sysinput = sys.stdin.buffer.readlinedef yes():print('Yes')exit()class UnionFind():def __init__(self, n):self.n = nself.root = [-1] * (n + 1)self.rnk = [0] * (n + 1)def find_root(self, x):while self.root[x] >= 0:x = self.root[x]return xdef unite(self, x, y):x = self.find_root(x)y = self.find_root(y)if x == y:returnelif self.rnk[x] > self.rnk[y]:self.root[x] += self.root[y]self.root[y] = xelse:self.root[y] += self.root[x]self.root[x] = yif self.rnk[x] == self.rnk[y]:self.rnk[y] += 1def isSameGroup(self, x, y):return self.find_root(x) == self.find_root(y)def size(self, x):return -self.root[self.find_root(x)]N, M = map(int, input().split())adj = [[] for _ in range(N+1)]edge1 = []edge2 = []for _ in range(M):a, b, c = map(int, input().split())if c == 1:edge1.append((a, b))else:edge2.append((a, b))UF = UnionFind(N)for a, b in edge1:if UF.isSameGroup(a, b):yes()else:UF.unite(a, b)adj_new = [set() for _ in range(N+1)]adj_new_rev = [set() for _ in range(N+1)]for a, b in edge2:ar = UF.find_root(a)br = UF.find_root(b)adj_new[ar].add(br)adj_new_rev[br].add(ar)cnt = 0st = []in_num = [0] * (N+1)for v in range(1, N+1):if len(adj_new_rev[v]) == 0:st.append(v)else:in_num[v] = len(adj_new_rev[v])while st:v = st.pop()cnt += 1for u in adj_new[v]:in_num[u] -= 1if in_num[u] == 0:st.append(u)if cnt == N:print('No')else:print('Yes')if __name__ == '__main__':main()