結果

問題 No.1400 すごろくで世界旅行
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 13:56:54
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 2,633 bytes
コンパイル時間 252 ms
コンパイル使用メモリ 82,408 KB
実行使用メモリ 371,112 KB
最終ジャッジ日時 2025-06-12 13:57:16
合計ジャッジ時間 4,938 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 15 WA * 1 MLE * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import math
from collections import deque

def main():
    V, D = map(int, sys.stdin.readline().split())
    E = []
    for _ in range(V):
        row = sys.stdin.readline().strip()
        E.append([1 if c == '1' else 0 for c in row])
    
    # Check if all vertices have at least one outgoing edge
    for i in range(V):
        if sum(E[i]) == 0:
            print("No")
            return
    
    # Check if the graph is strongly connected using Kosaraju's algorithm
    adj = [[] for _ in range(V)]
    reverse_adj = [[] for _ in range(V)]
    for i in range(V):
        for j in range(V):
            if E[i][j]:
                adj[i].append(j)
                reverse_adj[j].append(i)
    
    visited = [False] * V
    order = []
    for i in range(V):
        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(adj[node]):
                    if not visited[neighbor]:
                        stack.append((neighbor, False))
    
    visited = [False] * V
    component_count = 0
    for node in reversed(order):
        if not visited[node]:
            stack = [node]
            visited[node] = True
            while stack:
                u = stack.pop()
                for v in reverse_adj[u]:
                    if not visited[v]:
                        visited[v] = True
                        stack.append(v)
            component_count += 1
    
    if component_count != 1:
        print("No")
        return
    
    # Compute the GCD of cycle lengths starting from vertex 0
    def compute_gcd(s):
        dist = [-1] * V
        q = deque([s])
        dist[s] = 0
        current_gcd = 0
        while q:
            u = q.popleft()
            for v in adj[u]:
                if v == s:
                    cycle_length = dist[u] + 1
                    current_gcd = math.gcd(current_gcd, cycle_length)
                if dist[v] == -1:
                    dist[v] = dist[u] + 1
                    q.append(v)
                else:
                    cycle_length = dist[u] + 1 - dist[v]
                    current_gcd = math.gcd(current_gcd, cycle_length)
        return current_gcd
    
    gcd_cycle = compute_gcd(0)
    if gcd_cycle != 1:
        print("No")
    else:
        print("Yes")

if __name__ == "__main__":
    main()
0