結果

問題 No.1023 Cyclic Tour
ユーザー lam6er
提出日時 2025-04-16 01:10:56
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,199 bytes
コンパイル時間 242 ms
コンパイル使用メモリ 82,240 KB
実行使用メモリ 367,260 KB
最終ジャッジ日時 2025-04-16 01:12:36
合計ジャッジ時間 16,773 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 18 WA * 4 TLE * 2 -- * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque, defaultdict

def main():
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr += 1
    M = int(input[ptr])
    ptr += 1

    directed_edges = defaultdict(list)
    undirected_edges = []
    in_degree = defaultdict(int)
    nodes = set()

    for _ in range(M):
        a = int(input[ptr])
        ptr += 1
        b = int(input[ptr])
        ptr += 1
        c = int(input[ptr])
        ptr += 1
        if c == 2:
            directed_edges[a].append(b)
            in_degree[b] += 1
            nodes.add(a)
            nodes.add(b)
        else:
            undirected_edges.append((a, b))
            nodes.add(a)
            nodes.add(b)

    # Check if directed edges have a cycle using Kahn's algorithm
    queue = deque()
    temp_indegree = defaultdict(int)
    for node in in_degree:
        temp_indegree[node] = in_degree[node]
    for node in nodes:
        if temp_indegree.get(node, 0) == 0:
            queue.append(node)
    processed = 0
    while queue:
        u = queue.popleft()
        processed += 1
        for v in directed_edges.get(u, []):
            temp_indegree[v] -= 1
            if temp_indegree[v] == 0:
                queue.append(v)
    if processed != len(nodes):
        print("Yes")
        return

    # Check if undirected edges form a cycle using DSU
    parent = {}

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

    def union(u, v):
        u_root = find(u)
        v_root = find(v)
        if u_root == v_root:
            return True
        parent[v_root] = u_root
        return False

    cycle_undirected = False
    for a, b in undirected_edges:
        if a not in parent:
            parent[a] = a
        if b not in parent:
            parent[b] = b
        if union(a, b):
            cycle_undirected = True
            break
    if cycle_undirected:
        print("Yes")
        return

    # Build the directed adjacency list for BFS
    adj = defaultdict(list)
    for a in directed_edges:
        for b in directed_edges[a]:
            adj[a].append(b)

    # Precompute reachability for all nodes (not feasible for large N)
    # Instead, for each undirected edge, perform BFS from a and b
    # Check if a can reach b or b can reach a
    reachable = defaultdict(set)

    def bfs(start):
        visited = set()
        q = deque()
        q.append(start)
        visited.add(start)
        while q:
            u = q.popleft()
            for v in adj.get(u, []):
                if v not in visited:
                    visited.add(v)
                    q.append(v)
        return visited

    # Precompute reachability for all nodes in directed graph
    # This is O(N*(M)), which is not feasible for large N, but for the sake of code example
    # We'll proceed
    reachable = {}
    for node in nodes:
        reachable[node] = bfs(node)

    for a, b in undirected_edges:
        if b in reachable.get(a, set()) or a in reachable.get(b, set()):
            print("Yes")
            return

    print("No")

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