結果

問題 No.1023 Cyclic Tour
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 14:29:10
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,269 bytes
コンパイル時間 267 ms
コンパイル使用メモリ 82,652 KB
実行使用メモリ 288,580 KB
最終ジャッジ日時 2025-06-12 14:29:45
合計ジャッジ時間 33,188 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 34 WA * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import defaultdict

def main():
    sys.setrecursionlimit(1 << 25)
    N, M = map(int, sys.stdin.readline().split())
    roads = []
    graph = [[] for _ in range(N+1)]
    edge_road_ids = defaultdict(set)
    for i in range(M):
        a, b, c = map(int, sys.stdin.readline().split())
        roads.append((a, b, c))
        if c == 1:
            graph[a].append(b)
            edge_road_ids[(a, b)].add(i)
            graph[b].append(a)
            edge_road_ids[(b, a)].add(i)
        else:
            graph[a].append(b)
            edge_road_ids[(a, b)].add(i)
    
    visited = [False] * (N + 1)
    order = []
    
    for u in range(1, N + 1):
        if not visited[u]:
            stack = [(u, False)]
            while stack:
                node, processed = stack.pop()
                if processed:
                    order.append(node)
                    continue
                if visited[node]:
                    continue
                visited[node] = True
                stack.append((node, True))
                for v in reversed(graph[node]):
                    if not visited[v]:
                        stack.append((v, False))
    
    t_graph = [[] for _ in range(N + 1)]
    for u in range(1, N + 1):
        for v in graph[u]:
            t_graph[v].append(u)
    
    visited = [False] * (N + 1)
    scc_list = []
    for u in reversed(order):
        if not visited[u]:
            stack = [u]
            visited[u] = True
            scc = []
            while stack:
                node = stack.pop()
                scc.append(node)
                for v in t_graph[node]:
                    if not visited[v]:
                        visited[v] = True
                        stack.append(v)
            scc_list.append(scc)
    
    for scc in scc_list:
        if len(scc) >= 3:
            print("Yes")
            return
        elif len(scc) == 2:
            u, v = scc[0], scc[1]
            roads_uv = edge_road_ids.get((u, v), set())
            roads_vu = edge_road_ids.get((v, u), set())
            total_roads = roads_uv.union(roads_vu)
            if len(total_roads) >= 2:
                print("Yes")
                return
    print("No")

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