結果

問題 No.1983 [Cherry 4th Tune C] 南の島のマーメイド
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 20:33:57
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,568 bytes
コンパイル時間 250 ms
コンパイル使用メモリ 81,980 KB
実行使用メモリ 376,172 KB
最終ジャッジ日時 2025-06-12 20:35:20
合計ジャッジ時間 39,972 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 16 WA * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

def main():
    sys.setrecursionlimit(1 << 25)
    N, M, Q = map(int, sys.stdin.readline().split())
    edges = [[] for _ in range(N+1)]
    edge_map = {}
    for idx in range(M):
        u, v = map(int, sys.stdin.readline().split())
        edges[u].append((v, idx))
        edges[v].append((u, idx))
        edge_map[(u, v)] = idx
        edge_map[(v, u)] = idx

    # Compute bridges using Tarjan's algorithm
    disc = [-1] * (N + 1)
    low = [-1] * (N + 1)
    parent = [-1] * (N + 1)
    time_counter = [1]
    bridges = set()

    def tarjan(u):
        disc[u] = low[u] = time_counter[0]
        time_counter[0] += 1
        for (v, idx) in edges[u]:
            if disc[v] == -1:
                parent[v] = u
                tarjan(v)
                low[u] = min(low[u], low[v])
                if low[v] > disc[u]:
                    bridges.add(idx)
            elif v != parent[u]:
                low[u] = min(low[u], disc[v])

    for u in range(1, N+1):
        if disc[u] == -1:
            tarjan(u)

    # Build non-bridge adjacency list
    non_bridge_adj = [[] for _ in range(N+1)]
    for u in range(1, N+1):
        for (v, idx) in edges[u]:
            if idx not in bridges:
                non_bridge_adj[u].append(v)

    # Compute 2-edge-connected components (bcc)
    bcc = [-1] * (N + 1)
    bcc_id = 0
    for u in range(1, N+1):
        if bcc[u] == -1:
            queue = deque()
            queue.append(u)
            bcc[u] = bcc_id
            while queue:
                current = queue.popleft()
                for v in non_bridge_adj[current]:
                    if bcc[v] == -1:
                        bcc[v] = bcc_id
                        queue.append(v)
            bcc_id += 1

    # Compute connected components (cc) using original edges
    cc = [-1] * (N + 1)
    cc_id = 0
    for u in range(1, N+1):
        if cc[u] == -1:
            queue = deque()
            queue.append(u)
            cc[u] = cc_id
            while queue:
                current = queue.popleft()
                for (v, _) in edges[current]:
                    if cc[v] == -1:
                        cc[v] = cc_id
                        queue.append(v)
            cc_id += 1

    # Process queries
    for _ in range(Q):
        x, y = map(int, sys.stdin.readline().split())
        if cc[x] != cc[y]:
            print("No")
        else:
            if bcc[x] == bcc[y]:
                print("No")
            else:
                print("Yes")

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