結果

問題 No.1023 Cyclic Tour
ユーザー gew1fw
提出日時 2025-06-12 18:50:31
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,171 bytes
コンパイル時間 230 ms
コンパイル使用メモリ 82,468 KB
実行使用メモリ 395,428 KB
最終ジャッジ日時 2025-06-12 18:50:55
合計ジャッジ時間 18,850 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 18 WA * 4 TLE * 2 -- * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from sys import stdin
from collections import defaultdict, deque

def main():
    sys.setrecursionlimit(1 << 25)
    n, m = map(int, stdin.readline().split())
    directed_edges = []
    undirected_edges = []
    for _ in range(m):
        a, b, c = map(int, stdin.readline().split())
        if c == 1:
            undirected_edges.append((a, b))
        else:
            directed_edges.append((a, b))

    # Step 1: Check if directed graph has a cycle
    adj = [[] for _ in range(n+1)]
    for a, b in directed_edges:
        adj[a].append(b)

    index = 0
    indices = [0] * (n + 1)
    low = [0] * (n + 1)
    on_stack = [False] * (n + 1)
    stack = []
    sccs = []
    has_cycle = False

    def strongconnect(v):
        nonlocal index
        index += 1
        indices[v] = index
        low[v] = index
        stack.append(v)
        on_stack[v] = True
        for w in adj[v]:
            if indices[w] == 0:
                strongconnect(w)
                low[v] = min(low[v], low[w])
            elif on_stack[w]:
                low[v] = min(low[v], indices[w])
        if low[v] == indices[v]:
            scc = []
            while True:
                w = stack.pop()
                on_stack[w] = False
                scc.append(w)
                if w == v:
                    break
            sccs.append(scc)
            if len(scc) >= 2:
                nonlocal has_cycle
                has_cycle = True

    for v in range(1, n + 1):
        if indices[v] == 0:
            strongconnect(v)
    if has_cycle:
        print("Yes")
        return

    # Step 2: Check if any undirected edge's endpoints are in the same SCC of directed graph
    node_to_scc = {}
    for i, scc in enumerate(sccs):
        for node in scc:
            node_to_scc[node] = i

    for a, b in undirected_edges:
        if node_to_scc.get(a, -1) == node_to_scc.get(b, -2):
            print("Yes")
            return

    # Step 3: Check if undirected edges form a cycle
    parent = list(range(n + 1))

    def find(u):
        while parent[u] != u:
            parent[u] = parent[parent[u]]
            u = parent[u]
        return u

    for a, b in undirected_edges:
        u_root = find(a)
        v_root = find(b)
        if u_root == v_root:
            print("Yes")
            return
        parent[v_root] = u_root

    # Step 4: Check for each undirected edge if u can reach v or v can reach u in directed graph
    adj_dir = [[] for _ in range(n + 1)]
    for a, b in directed_edges:
        adj_dir[a].append(b)

    # Precompute for each node, the nodes it can reach using BFS
    reachable = [set() for _ in range(n + 1)]
    for u in range(1, n + 1):
        visited = set()
        q = deque([u])
        visited.add(u)
        while q:
            current = q.popleft()
            for v in adj_dir[current]:
                if v not in visited:
                    visited.add(v)
                    q.append(v)
        reachable[u] = visited

    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