結果

問題 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
権限があれば一括ダウンロードができます

ソースコード

diff #

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()
0