結果
問題 |
No.1023 Cyclic Tour
|
ユーザー |
![]() |
提出日時 | 2025-03-31 17:38:34 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 5,794 bytes |
コンパイル時間 | 217 ms |
コンパイル使用メモリ | 82,696 KB |
実行使用メモリ | 156,356 KB |
最終ジャッジ日時 | 2025-03-31 17:39:31 |
合計ジャッジ時間 | 6,559 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 4 TLE * 1 -- * 44 |
ソースコード
import sys from collections import defaultdict, deque def main(): sys.setrecursionlimit(1 << 25) N, M = map(int, sys.stdin.readline().split()) edges = [] undirected_edges = [] directed_edges = [] for _ in range(M): a, b, c = map(int, sys.stdin.readline().split()) edges.append((a, b, c)) if c == 1: undirected_edges.append((a, b)) else: directed_edges.append((a, b)) # Step 1: Check if any undirected component has a cycle class UnionFind: def __init__(self, size): self.parent = list(range(size + 1)) # 1-based self.size = [1] * (size + 1) # size of the component self.edge_count = [0] * (size + 1) # number of undirected edges in the component def find(self, x): if self.parent[x] != x: self.parent[x] = self.find(self.parent[x]) return self.parent[x] def unite(self, x, y): x_root = self.find(x) y_root = self.find(y) if x_root == y_root: self.edge_count[x_root] += 1 return if self.size[x_root] < self.size[y_root]: x_root, y_root = y_root, x_root self.parent[y_root] = x_root self.size[x_root] += self.size[y_root] self.edge_count[x_root] += self.edge_count[y_root] + 1 # current edge is added uf = UnionFind(N) for a, b in undirected_edges: uf.unite(a, b) # Check each root for edge count >= vertex count roots = set() component_info = defaultdict(lambda: {'vertices': 0, 'edges': 0}) for node in range(1, N + 1): root = uf.find(node) roots.add(root) component_info[root]['vertices'] = uf.size[root] component_info[root]['edges'] = uf.edge_count[root] for root in roots: if component_info[root]['edges'] >= component_info[root]['vertices']: print("Yes") return # Step 2: Check for back edges in directed edges within the same component (which are trees) # Precompute in-time and out-time for each node in each tree component in_time = {} out_time = {} visited_components = set() # to track which components have been processed component_vertices = defaultdict(list) for node in range(1, N + 1): root = uf.find(node) component_vertices[root].append(node) for root in component_vertices: # Skip components that are not trees (edge count == vertices -1) if component_info[root]['edges'] != component_info[root]['vertices'] - 1: continue vertices = component_vertices[root] # Build adjacency list for the undirected edges in this component adj = defaultdict(list) for a, b in undirected_edges: ra = uf.find(a) rb = uf.find(b) if ra == root and rb == root: adj[a].append(b) adj[b].append(a) # DFS to compute in and out times in_time_root = {} out_time_root = {} parent = {} time = 0 stack = [(root, None, False)] # (node, parent, is_visited) while stack: node, p, is_visited = stack.pop() if is_visited: out_time_root[node] = time time += 1 continue if node in in_time_root: continue parent[node] = p in_time_root[node] = time time += 1 stack.append((node, p, True)) # Push children in reverse order to process in correct DFS order neighbors = adj[node] for neighbor in reversed(neighbors): if neighbor != p: stack.append((neighbor, node, False)) # Save in and out times for this component in_time.update(in_time_root) out_time.update(out_time_root) # Now, check all directed edges (c=2) for back edges in their component for a, b in directed_edges: root_a = uf.find(a) root_b = uf.find(b) if root_a != root_b: continue if component_info[root_a]['edges'] != component_info[root_a]['vertices'] -1: continue # Check if b is an ancestor of a in the DFS tree # a's in_time is >= b's in_time and a's out_time <= b's out_time if a not in in_time or b not in in_time: continue # should not happen if in_time[b] <= in_time[a] and out_time[a] <= out_time[b]: print("Yes") return # Step 3: Check for cycles in the condensed graph of components connected by directed edges # Build condensed graph condensed_adj = defaultdict(set) in_degree = defaultdict(int) # Nodes are the roots condensed_nodes = list(roots) for a, b in directed_edges: root_a = uf.find(a) root_b = uf.find(b) if root_a == root_b: continue # same component, handled in step 2 if root_b not in condensed_adj[root_a]: condensed_adj[root_a].add(root_b) in_degree[root_b] += 1 # Kahn's algorithm for topological sort queue = deque() for node in condensed_nodes: if in_degree.get(node, 0) == 0: queue.append(node) processed = 0 while queue: u = queue.popleft() processed += 1 for v in condensed_adj[u]: in_degree[v] -= 1 if in_degree[v] == 0: queue.append(v) # Check if processed all nodes in condensed graph if processed != len(condensed_nodes): print("Yes") else: print("No") if __name__ == "__main__": main()