結果
| 問題 |
No.1023 Cyclic Tour
|
| コンテスト | |
| ユーザー |
 lam6er
|
| 提出日時 | 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()