結果

問題 No.1400 すごろくで世界旅行
コンテスト
ユーザー lam6er
提出日時 2025-04-16 16:23:52
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 2,685 bytes
コンパイル時間 364 ms
コンパイル使用メモリ 81,548 KB
実行使用メモリ 370,768 KB
最終ジャッジ日時 2025-04-16 16:24:42
合計ジャッジ時間 4,763 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 15 WA * 1 MLE * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

def main():
    sys.setrecursionlimit(1 << 25)
    V, D = map(int, sys.stdin.readline().split())
    E = []
    for _ in range(V):
        s = sys.stdin.readline().strip()
        E.append([int(c) for c in s])
    
    # Check out-degree for each vertex
    for i in range(V):
        if sum(E[i]) == 0:
            print("No")
            return
    
    # Check strong connectivity using Kosaraju's algorithm
    # Build adjacency list
    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] == 1:
                adj[i].append(j)
                reverse_adj[j].append(i)
    
    visited = [False] * V
    order = []
    
    def dfs(u):
        stack = [(u, 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 v in adj[node]:
                if not visited[v]:
                    stack.append((v, False))
    
    for i in range(V):
        if not visited[i]:
            dfs(i)
    
    visited = [False] * V
    component = [0] * V
    label = 0
    
    def reverse_dfs(u, label):
        stack = [u]
        visited[u] = True
        component[u] = label
        while stack:
            node = stack.pop()
            for v in reverse_adj[node]:
                if not visited[v]:
                    visited[v] = True
                    component[v] = label
                    stack.append(v)
    
    for i in reversed(order):
        if not visited[i]:
            reverse_dfs(i, label)
            label += 1
    
    if label != 1:
        print("No")
        return
    
    # Check for self-loop
    has_self_loop = any(E[i][i] == 1 for i in range(V))
    if has_self_loop:
        print("Yes")
        return
    
    # Check if there exists a vertex with both even and odd cycles
    # BFS from vertex 0
    start = 0
    # Each node has two states: even and odd steps
    visited = [[False] * 2 for _ in range(V)]
    q = deque()
    q.append((start, 0))
    visited[start][0] = True  # even steps
    
    while q:
        u, parity = q.popleft()
        for v in adj[u]:
            new_parity = 1 - parity
            if not visited[v][new_parity]:
                visited[v][new_parity] = True
                q.append((v, new_parity))
    
    if visited[start][0] and visited[start][1]:
        print("Yes")
    else:
        print("No")

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