結果

問題 No.1983 [Cherry 4th Tune C] 南の島のマーメイド
コンテスト
ユーザー lam6er
提出日時 2025-04-15 20:59:25
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,893 bytes
コンパイル時間 576 ms
コンパイル使用メモリ 82,124 KB
実行使用メモリ 262,328 KB
最終ジャッジ日時 2025-04-15 21:02:34
合計ジャッジ時間 27,641 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 16 WA * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from sys import stdin

sys.setrecursionlimit(1 << 25)

class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size + 1))  # 1-based indexing
        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

def main():
    data = list(map(int, stdin.read().split()))
    ptr = 0
    N = data[ptr]
    M = data[ptr + 1]
    Q = data[ptr + 2]
    ptr += 3
    
    edges = []
    adj = [[] for _ in range(N + 1)]
    for _ in range(M):
        u = data[ptr]
        v = data[ptr + 1]
        edges.append((u, v))
        adj[u].append(v)
        adj[v].append(u)
        ptr += 2
    
    # Tarjan's algorithm to find bridges iteratively
    bridges = set()
    disc = [0] * (N + 1)
    low = [0] * (N + 1)
    visited = [False] * (N + 1)
    time = 1
    
    for u in range(1, N + 1):
        if not visited[u]:
            stack = [(u, None, False)]
            while stack:
                node, parent_node, is_processed = stack.pop()
                if not is_processed:
                    if visited[node]:
                        continue
                    visited[node] = True
                    disc[node] = time
                    low[node] = time
                    time += 1
                    stack.append((node, parent_node, True))
                    # Push children in reverse order to process them in the original order
                    for v in reversed(adj[node]):
                        if v == parent_node:
                            continue
                        if not visited[v]:
                            stack.append((v, node, False))
                        else:
                            # Back edge, update low
                            if disc[v] < low[node]:
                                low[node] = disc[v]
                else:
                    # Process the node after children
                    for v in adj[node]:
                        if v == parent_node:
                            continue
                        if disc[v] > disc[node]:  # Child in DFS tree
                            if low[v] < low[node]:
                                low[node] = low[v]
                            if low[v] > disc[node]:
                                bridges.add(frozenset({node, v}))
                    # Update parent's low if applicable
                    if parent_node is not None:
                        if low[node] < low[parent_node]:
                            low[parent_node] = low[node]
    
    # Build connected components using all edges
    connected_components_uf = UnionFind(N)
    for u, v in edges:
        connected_components_uf.union(u, v)
    
    # Build two-edge-connected components using non-bridge edges
    two_edge_components_uf = UnionFind(N)
    for u, v in edges:
        if frozenset({u, v}) not in bridges:
            two_edge_components_uf.union(u, v)
    
    # Process queries
    output = []
    for _ in range(Q):
        x = data[ptr]
        y = data[ptr + 1]
        ptr += 2
        if connected_components_uf.find(x) != connected_components_uf.find(y):
            output.append("No")
        else:
            if two_edge_components_uf.find(x) == two_edge_components_uf.find(y):
                output.append("No")
            else:
                output.append("Yes")
    
    print('\n'.join(output))

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