結果
問題 |
No.1023 Cyclic Tour
|
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
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()