結果

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

ソースコード

diff # 

import sys
from collections import deque

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

    # Check if all vertices have at least one outgoing edge
    for i in range(V):
        if '1' not in E[i]:
            print("No")
            return

    # Check strong connectivity using Kosaraju's algorithm
    # Step 1: Perform DFS on the original graph to get the order
    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 j in reversed(range(V)):
                    if E[node][j] == '1' and not visited[j]:
                        stack.append((j, False))

    # Step 2: Perform DFS on the transposed graph in reverse order
    visited = [False] * V
    components = 0
    transposed_E = [[] for _ in range(V)]
    for i in range(V):
        for j in range(V):
            if E[i][j] == '1':
                transposed_E[j].append(i)

    for node in reversed(order):
        if not visited[node]:
            stack = [node]
            visited[node] = True
            while stack:
                u = stack.pop()
                for v in transposed_E[u]:
                    if not visited[v]:
                        visited[v] = True
                        stack.append(v)
            components += 1
            if components > 1:
                print("No")
                return

    # Check bipartiteness
    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:
                v = queue.popleft()
                for u in range(V):
                    if E[v][u] == '1':
                        if color[u] == -1:
                            color[u] = color[v] ^ 1
                            queue.append(u)
                        elif color[u] == color[v]:
                            is_bipartite = False
                            break
                if not is_bipartite:
                    break
            if not is_bipartite:
                break

    if not is_bipartite:
        print("Yes")
    else:
        # Check for self-loop
        has_self_loop = any(E[i][i] == '1' for i in range(V))
        if has_self_loop:
            print("Yes")
        else:
            print("No")

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