結果

問題 No.1983 [Cherry 4th Tune C] 南の島のマーメイド
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 19:57:24
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,873 bytes
コンパイル時間 206 ms
コンパイル使用メモリ 82,632 KB
実行使用メモリ 220,464 KB
最終ジャッジ日時 2025-06-12 19:59:22
合計ジャッジ時間 24,392 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 16 WA * 25
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
from sys import stdin

def main():
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr]); ptr += 1
    M = int(input[ptr]); ptr += 1
    Q = int(input[ptr]); ptr += 1

    edges = []
    adj = [[] for _ in range(N + 1)]  # 1-based indexing

    for i in range(M):
        u = int(input[ptr]); ptr += 1
        v = int(input[ptr]); ptr += 1
        edges.append((u, v))
        adj[u].append((v, i))
        adj[v].append((u, i))

    # DSU for original connected components
    class DSU:
        def __init__(self, size):
            self.parent = list(range(size + 1))
            self.rank = [0] * (size + 1)

        def find(self, x):
            if self.parent[x] != x:
                self.parent[x] = self.find(self.parent[x])
            return self.parent[x]

        def union(self, x, y):
            x_root = self.find(x)
            y_root = self.find(y)
            if x_root == y_root:
                return
            if self.rank[x_root] < self.rank[y_root]:
                self.parent[x_root] = y_root
            else:
                self.parent[y_root] = x_root
                if self.rank[x_root] == self.rank[y_root]:
                    self.rank[x_root] += 1

    dsu = DSU(N)
    for u, v in edges:
        dsu.union(u, v)

    # Tarjan's algorithm to find bridges
    is_bridge = [False] * M
    disc = [-1] * (N + 1)
    low = [-1] * (N + 1)
    time = 0

    for u in range(1, N + 1):
        if disc[u] == -1:
            stack = [(u, -1, False)]  # (node, parent_edge_idx, visited)
            while stack:
                node, parent_edge, visited = stack.pop()
                if visited:
                    for v, edge_idx in adj[node]:
                        if edge_idx == parent_edge:
                            continue
                        if disc[v] > disc[node]:  # Tree edge
                            if low[v] < low[node]:
                                low[node] = low[v]
                            if low[v] > disc[node]:
                                is_bridge[edge_idx] = True
                        else:
                            low[node] = min(low[node], disc[v])
                    continue
                if disc[node] != -1:
                    continue
                disc[node] = low[node] = time
                time += 1
                stack.append((node, parent_edge, True))
                # Push children
                for v, edge_idx in adj[node]:
                    if edge_idx == parent_edge:
                        continue
                    if disc[v] == -1:
                        stack.append((v, edge_idx, False))
                    else:
                        low[node] = min(low[node], disc[v])

    # Build adjacency list without bridges
    adj_non_bridge = [[] for _ in range(N + 1)]
    for i in range(M):
        if not is_bridge[i]:
            u, v = edges[i]
            adj_non_bridge[u].append(v)
            adj_non_bridge[v].append(u)

    # Compute 2-edge-connected components
    bcc_id = [-1] * (N + 1)
    current_id = 0
    for u in range(1, N + 1):
        if bcc_id[u] == -1:
            stack = [u]
            bcc_id[u] = current_id
            while stack:
                node = stack.pop()
                for v in adj_non_bridge[node]:
                    if bcc_id[v] == -1:
                        bcc_id[v] = current_id
                        stack.append(v)
            current_id += 1

    # Process queries
    output = []
    for _ in range(Q):
        x = int(input[ptr]); ptr += 1
        y = int(input[ptr]); ptr += 1
        if dsu.find(x) != dsu.find(y):
            output.append("No")
        else:
            if bcc_id[x] == bcc_id[y]:
                output.append("No")
            else:
                output.append("Yes")

    print('\n'.join(output))

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