結果

問題 No.1023 Cyclic Tour
ユーザー lam6er
提出日時 2025-03-20 21:16:58
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 4,850 bytes
コンパイル時間 275 ms
コンパイル使用メモリ 82,512 KB
実行使用メモリ 209,748 KB
最終ジャッジ日時 2025-03-20 21:18:18
合計ジャッジ時間 28,039 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 46 WA * 3
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import sys
from collections import defaultdict, deque
sys.setrecursionlimit(1 << 25)
class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size + 1))
        self.rank = [0] * (size + 1)
    
    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 = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    idx = 0
    N = int(data[idx])
    idx += 1
    M = int(data[idx])
    idx +=1
    
    undirected = []
    directed = []
    directed_edges_set = set()
    
    for _ in range(M):
        a = int(data[idx])
        idx +=1
        b = int(data[idx])
        idx +=1
        c = int(data[idx])
        idx +=1
        if c == 1:
            undirected.append( (a, b) )
        else:
            directed.append( (a, b) )
            directed_edges_set.add( (a, b) )
    
    # Step 1: Check cycles in undirected subgraph
    uf = UnionFind(N)
    for a, b in undirected:
        uf.unite(a, b)
    
    uni_v = defaultdict(int)
    uni_e = defaultdict(int)
    
    for i in range(1, N+1):
        root = uf.find(i)
        uni_v[root] += 1
    
    for a, b in undirected:
        root_a = uf.find(a)
        root_b = uf.find(b)
        if root_a == root_b:
            uni_e[root_a] += 1
    
    for root in uni_v:
        if uni_e[root] >= uni_v[root]:
            print("Yes")
            return
    
    # Step 2: Check cycles in directed subgraph using SCC
    graph = [[] for _ in range(N+1)]
    for a, b in directed:
        graph[a].append(b)
    
    visited = [False] * (N + 1)
    order = []
    
    for i in range(1, N + 1):
        if not visited[i]:
            stack = [(i, False)]
            while stack:
                node, processed = stack.pop()
                if processed:
                    order.append(node)
                    continue
                if visited[node]:
                    continue
                visited[node] = True
                stack.append( (node, True) )
                for neighbor in reversed(graph[node]):
                    if not visited[neighbor]:
                        stack.append( (neighbor, False) )
    
    visited = [False] * (N + 1)
    components = []
    reverse_graph = [[] for _ in range(N+1)]
    for v in range(1, N+1):
        for u in graph[v]:
            reverse_graph[u].append(v)
    
    for v in reversed(order):
        if not visited[v]:
            component = []
            stack = [v]
            visited[v] = True
            while stack:
                node = stack.pop()
                component.append(node)
                for neighbor in reverse_graph[node]:
                    if not visited[neighbor]:
                        visited[neighbor] = True
                        stack.append(neighbor)
            components.append(component)
    
    for comp in components:
        if len(comp) >= 2:
            print("Yes")
            return
    
    # Step 3: Check if any undirected edge's reverse is a directed edge
    for a, b in undirected:
        if (b, a) in directed_edges_set:
            print("Yes")
            return
    
    # Step 4: Contract the graph and check for cycles
    component_representative = {}
    for i in range(1, N+1):
        component_representative[i] = uf.find(i)
    
    comp_ids = {}
    id_counter = 0
    for root in component_representative.values():
        if root not in comp_ids:
            comp_ids[root] = id_counter
            id_counter += 1
    
    nodes = id_counter
    contracted_graph = [[] for _ in range(nodes)]
    edge_set = set()
    
    for a, b in directed:
        a_root = component_representative[a]
        b_root = component_representative[b]
        u = comp_ids[a_root]
        v = comp_ids[b_root]
        if u != v and (u, v) not in edge_set:
            contracted_graph[u].append(v)
            edge_set.add( (u, v) )
    
    # Check if DAG
    in_degree = [0] * nodes
    for u in range(nodes):
        for v in contracted_graph[u]:
            in_degree[v] += 1
    
    q = deque()
    for u in range(nodes):
        if in_degree[u] == 0:
            q.append(u)
    
    visited = 0
    while q:
        u = q.popleft()
        visited += 1
        for v in contracted_graph[u]:
            in_degree[v] -= 1
            if in_degree[v] == 0:
                q.append(v)
    
    if visited != nodes:
        print("Yes")
        return
    
    print("No")
if __name__ == "__main__":
    main()
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0