結果

問題 No.1023 Cyclic Tour
ユーザー chineristAC
提出日時 2020-10-08 17:01:00
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 986 ms / 2,000 ms
コード長 2,273 bytes
コンパイル時間 209 ms
コンパイル使用メモリ 82,688 KB
実行使用メモリ 113,568 KB
最終ジャッジ日時 2024-07-20 05:58:51
合計ジャッジ時間 27,205 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 49
権限があれば一括ダウンロードができます

ソースコード

diff # 

class UnionFindVerSize():
    def __init__(self, N):
        self._parent = [n for n in range(0, N)]
        self._size = [1] * N
        self.edge = [[] for i in range(N)]
        self.deg = [0 for i in range(N)]

    def find_root(self, x):
        if self._parent[x] == x: return x
        self._parent[x] = self.find_root(self._parent[x])
        return self._parent[x]

    def unite(self, x, y):
        gx = self.find_root(x)
        gy = self.find_root(y)
        if gx == gy: return

        if self._size[gx] < self._size[gy]:
            self._parent[gx] = gy
            self._size[gy] += self._size[gx]
            self.edge[gy] += self.edge[gx]
            self.edge[gx] = []
        else:
            self._parent[gy] = gx
            self._size[gx] += self._size[gy]
            self.edge[gx] += self.edge[gy]
            self.edge[gy] = []

    def add_edge(self,x,y):
        gx = self.find_root(x)
        gy = self.find_root(y)
        self.edge[gx].append(gy)

    def get_size(self, x):
        return self._size[self.find_root(x)]

    def is_same_group(self, x, y):
        return self.find_root(x) == self.find_root(y)

    def calc_group_num(self):
        N = len(self._parent)
        ans = 0
        for i in range(N):
            if self.find_root(i) == i:
                ans += 1
        return ans

    def rebuild(self):
        for i in range(N):
            if self.edge[i]:
                self.edge[i] = [self.find_root(v) for v in self.edge[i]]
                for v in self.edge[i]:
                    self.deg[v] += 1

import sys
from collections import deque

input = sys.stdin.readline

N,M = map(int,input().split())
uf = UnionFindVerSize(N)
uf_un = UnionFindVerSize(N)
for i in range(M):
    a,b,c = map(int,input().split())
    if c==1:
        uf.unite(a-1,b-1)
        if uf_un.is_same_group(a-1,b-1):
            print("Yes")
            exit()
        uf_un.unite(a-1,b-1)
    else:
        uf.add_edge(a-1,b-1)

uf.rebuild()

ans = [v for v in range(N) if uf.deg[v]==0]
deq = deque(ans)
used = [0]*N

while deq:
    v = deq.popleft()
    for nv in uf.edge[v]:
        uf.deg[nv] -= 1
        if uf.deg[nv] == 0:
            deq.append(nv)
            ans.append(nv)

if len(ans)==N:
    print("No")
else:
    print("Yes")
0