結果

問題 No.1023 Cyclic Tour
ユーザー ptotqptotq
提出日時 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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 44 ms
52,352 KB
testcase_01 AC 41 ms
52,352 KB
testcase_02 AC 44 ms
52,480 KB
testcase_03 AC 41 ms
52,480 KB
testcase_04 AC 190 ms
77,056 KB
testcase_05 AC 191 ms
77,056 KB
testcase_06 AC 191 ms
77,696 KB
testcase_07 AC 200 ms
77,440 KB
testcase_08 AC 257 ms
104,320 KB
testcase_09 AC 436 ms
117,760 KB
testcase_10 AC 434 ms
116,992 KB
testcase_11 AC 455 ms
120,064 KB
testcase_12 AC 481 ms
128,896 KB
testcase_13 AC 450 ms
125,952 KB
testcase_14 AC 452 ms
124,032 KB
testcase_15 AC 481 ms
126,976 KB
testcase_16 AC 1,064 ms
230,376 KB
testcase_17 AC 1,076 ms
231,524 KB
testcase_18 AC 958 ms
191,140 KB
testcase_19 AC 938 ms
188,456 KB
testcase_20 AC 364 ms
102,144 KB
testcase_21 AC 367 ms
102,400 KB
testcase_22 AC 461 ms
116,864 KB
testcase_23 AC 509 ms
117,248 KB
testcase_24 AC 556 ms
130,176 KB
testcase_25 AC 345 ms
103,424 KB
testcase_26 AC 354 ms
102,016 KB
testcase_27 AC 317 ms
98,944 KB
testcase_28 AC 555 ms
128,768 KB
testcase_29 AC 578 ms
133,120 KB
testcase_30 AC 556 ms
128,000 KB
testcase_31 AC 536 ms
127,616 KB
testcase_32 AC 679 ms
185,344 KB
testcase_33 AC 652 ms
160,640 KB
testcase_34 AC 114 ms
79,104 KB
testcase_35 AC 194 ms
82,304 KB
testcase_36 AC 419 ms
110,592 KB
testcase_37 AC 569 ms
140,288 KB
testcase_38 AC 605 ms
142,464 KB
testcase_39 AC 539 ms
119,680 KB
testcase_40 AC 539 ms
121,984 KB
testcase_41 AC 536 ms
120,960 KB
testcase_42 AC 313 ms
92,160 KB
testcase_43 AC 255 ms
98,944 KB
testcase_44 AC 236 ms
96,000 KB
testcase_45 AC 611 ms
258,560 KB
testcase_46 AC 803 ms
311,168 KB
testcase_47 AC 129 ms
88,704 KB
testcase_48 AC 203 ms
99,072 KB
testcase_49 AC 211 ms
98,944 KB
testcase_50 AC 193 ms
100,480 KB
testcase_51 AC 167 ms
83,840 KB
testcase_52 AC 172 ms
87,424 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)


class UnionFind(object):
    def __init__(self, n: int):
        self.nodes = [-1]*n

    def find(self, x: int) -> int:
        if self.nodes[x] < 0:
            return x
        else:
            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.nodes

        if root_x != root_y:
            if nodes[root_x] > nodes[root_y]:
                root_x, root_y = root_y, root_x
            nodes[root_x] += nodes[root_y]
            nodes[root_y] = root_x

        return root_x != root_y


def scc(N, G, RG):
    order = []
    used = [0]*N
    group = [None]*N

    def dfs(s):
        used[s] = 1
        for t in G[s]:
            if not used[t]:
                dfs(t)
        order.append(s)

    def rdfs(s, col):
        group[s] = col
        used[s] = 1
        for t in RG[s]:
            if not used[t]:
                rdfs(t, col)
    for i in range(N):
        if not used[i]:
            dfs(i)
    used = [0]*N
    label = 0
    for s in reversed(order):
        if not used[s]:
            rdfs(s, label)
            label += 1
    return label, group


if __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 -= 1
        v -= 1
        if 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')
0