結果

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

ソースコード

diff # 

import sys
from sys import stdin
from collections import deque

def main():
    sys.setrecursionlimit(1 << 25)
    V, D = map(int, stdin.readline().split())
    E = [stdin.readline().strip() for _ in range(V)]

    # Check strong connectivity using Kosaraju's algorithm
    # Build adjacency list
    adj = [[] for _ in range(V)]
    rev_adj = [[] for _ in range(V)]
    for i in range(V):
        for j in range(V):
            if E[i][j] == '1':
                adj[i].append(j)
                rev_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
    label = 0

    def reverse_dfs(u, label):
        stack = [u]
        visited[u] = True
        while stack:
            node = stack.pop()
            for v in rev_adj[node]:
                if not visited[v]:
                    visited[v] = True
                    stack.append(v)

    components = 0
    for u in reversed(order):
        if not visited[u]:
            reverse_dfs(u, label)
            components += 1
            label += 1

    if components != 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 bipartite
    color = [-1] * V
    is_bipartite = True
    for i in range(V):
        if color[i] == -1:
            queue = deque()
            queue.append(i)
            color[i] = 0
            while queue:
                u = queue.popleft()
                for v in adj[u]:
                    if color[v] == -1:
                        color[v] = color[u] ^ 1
                        queue.append(v)
                    elif color[v] == color[u]:
                        is_bipartite = False
                        break
                if not is_bipartite:
                    break
        if not is_bipartite:
            break

    if not is_bipartite:
        print("Yes")
    else:
        print("No")

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