結果

問題 No.1023 Cyclic Tour
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 13:50:51
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,981 bytes
コンパイル時間 349 ms
コンパイル使用メモリ 82,560 KB
実行使用メモリ 54,144 KB
最終ジャッジ日時 2025-06-12 13:51:34
合計ジャッジ時間 5,324 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other TLE * 1 -- * 48
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

def main():
    sys.setrecursionlimit(1 << 25)
    N, M = map(int, sys.stdin.readline().split())
    directed_edges = []
    undirected_edges = []
    adj_directed = [[] for _ in range(N+1)]  # For directed roads only
    for _ in range(M):
        a, b, c = map(int, sys.stdin.readline().split())
        if c == 1:
            undirected_edges.append((a, b))
        else:
            directed_edges.append((a, b))
            adj_directed[a].append(b)
    
    # Function to check if the directed graph has a cycle
    def has_cycle(adj, N):
        in_degree = [0] * (N+1)
        for a in range(1, N+1):
            for b in adj[a]:
                in_degree[b] += 1
        queue = deque()
        for i in range(1, N+1):
            if in_degree[i] == 0:
                queue.append(i)
        cnt = 0
        while queue:
            u = queue.popleft()
            cnt += 1
            for v in adj[u]:
                in_degree[v] -= 1
                if in_degree[v] == 0:
                    queue.append(v)
        return cnt != N
    
    if has_cycle(adj_directed, N):
        print("Yes")
        return
    
    # Build the directed graph (directed roads only) and compute reachability for each node
    # Precompute for each node the nodes it can reach
    reachable = [set() for _ in range(N+1)]
    for u in range(1, N+1):
        visited = [False] * (N+1)
        q = deque()
        q.append(u)
        visited[u] = True
        while q:
            current = q.popleft()
            for v in adj_directed[current]:
                if not visited[v]:
                    visited[v] = True
                    q.append(v)
        reachable[u] = set([i for i in range(1, N+1) if visited[i]])
    
    # Check each undirected edge
    for a, b in undirected_edges:
        if b in reachable[a] or a in reachable[b]:
            print("Yes")
            return
    
    print("No")

if __name__ == "__main__":
    main()
0