結果

問題 No.1023 Cyclic Tour
ユーザー ptotqptotq
提出日時 2020-04-10 22:55:52
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
AC  
実行時間 1,390 ms / 2,000 ms
コード長 2,004 bytes
コンパイル時間 105 ms
コンパイル使用メモリ 12,672 KB
実行使用メモリ 101,748 KB
最終ジャッジ日時 2024-09-15 23:20:39
合計ジャッジ時間 49,426 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 32 ms
10,880 KB
testcase_01 AC 30 ms
10,752 KB
testcase_02 AC 31 ms
10,752 KB
testcase_03 AC 31 ms
10,752 KB
testcase_04 AC 239 ms
12,288 KB
testcase_05 AC 245 ms
12,160 KB
testcase_06 AC 252 ms
12,544 KB
testcase_07 AC 244 ms
12,416 KB
testcase_08 AC 655 ms
65,664 KB
testcase_09 AC 750 ms
70,680 KB
testcase_10 AC 740 ms
70,676 KB
testcase_11 AC 806 ms
74,492 KB
testcase_12 AC 864 ms
76,536 KB
testcase_13 AC 831 ms
72,628 KB
testcase_14 AC 779 ms
71,976 KB
testcase_15 AC 850 ms
73,384 KB
testcase_16 AC 1,313 ms
93,868 KB
testcase_17 AC 1,332 ms
95,508 KB
testcase_18 AC 1,347 ms
94,396 KB
testcase_19 AC 1,362 ms
91,896 KB
testcase_20 AC 1,024 ms
82,724 KB
testcase_21 AC 1,068 ms
86,708 KB
testcase_22 AC 1,171 ms
93,496 KB
testcase_23 AC 1,223 ms
96,004 KB
testcase_24 AC 1,333 ms
99,832 KB
testcase_25 AC 1,078 ms
87,424 KB
testcase_26 AC 971 ms
80,580 KB
testcase_27 AC 854 ms
75,416 KB
testcase_28 AC 1,167 ms
97,180 KB
testcase_29 AC 1,158 ms
96,168 KB
testcase_30 AC 1,224 ms
99,552 KB
testcase_31 AC 1,215 ms
95,824 KB
testcase_32 AC 1,302 ms
101,320 KB
testcase_33 AC 1,390 ms
101,748 KB
testcase_34 AC 182 ms
18,176 KB
testcase_35 AC 398 ms
24,448 KB
testcase_36 AC 1,136 ms
90,736 KB
testcase_37 AC 1,188 ms
95,744 KB
testcase_38 AC 1,257 ms
95,228 KB
testcase_39 AC 1,182 ms
92,864 KB
testcase_40 AC 1,182 ms
93,480 KB
testcase_41 AC 1,137 ms
93,760 KB
testcase_42 AC 849 ms
72,832 KB
testcase_43 AC 811 ms
78,336 KB
testcase_44 AC 616 ms
65,636 KB
testcase_45 AC 988 ms
93,696 KB
testcase_46 AC 1,099 ms
96,268 KB
testcase_47 AC 636 ms
66,444 KB
testcase_48 AC 932 ms
83,052 KB
testcase_49 AC 945 ms
82,844 KB
testcase_50 AC 918 ms
82,492 KB
testcase_51 AC 780 ms
74,112 KB
testcase_52 AC 806 ms
70,912 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