結果

問題 No.1983 [Cherry 4th Tune C] 南の島のマーメイド
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 20:31:39
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,244 ms / 4,000 ms
コード長 3,658 bytes
コンパイル時間 333 ms
コンパイル使用メモリ 81,728 KB
実行使用メモリ 213,888 KB
最終ジャッジ日時 2025-06-12 20:32:52
合計ジャッジ時間 28,267 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 41
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import defaultdict

sys.setrecursionlimit(1 << 25)

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

    edges = []
    adj = [[] for _ in range(N+1)]
    for _ in range(M):
        u = int(data[idx])
        idx += 1
        v = int(data[idx])
        idx += 1
        edges.append((u, v))
        adj[u].append(v)
        adj[v].append(u)

    # Tarjan's algorithm to find bridges
    bridges = set()
    visited = [False] * (N + 1)
    disc = [float('inf')] * (N + 1)
    low = [float('inf')] * (N + 1)
    time_counter = [1]

    for i in range(1, N + 1):
        if not visited[i]:
            stack = []
            parent = {i: None}
            stack.append((i, None, False))
            while stack:
                current, parent_node, processed = stack.pop()
                if not processed:
                    if visited[current]:
                        continue
                    visited[current] = True
                    disc[current] = low[current] = time_counter[0]
                    time_counter[0] += 1
                    stack.append((current, parent_node, True))
                    for neighbor in adj[current]:
                        if not visited[neighbor]:
                            parent[neighbor] = current
                            stack.append((neighbor, current, False))
                        else:
                            if neighbor != parent_node:
                                low[current] = min(low[current], disc[neighbor])
                else:
                    for neighbor in adj[current]:
                        if parent.get(neighbor, None) == current:
                            low[current] = min(low[current], low[neighbor])
                            if low[neighbor] > disc[current]:
                                u = min(current, neighbor)
                                v = max(current, neighbor)
                                bridges.add((u, v))
                        elif neighbor != parent_node:
                            low[current] = min(low[current], disc[neighbor])

    # DSU for bridge-only edges
    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_bridge = DSU(N)
    for u, v in bridges:
        dsu_bridge.union(u, v)

    # DSU for original graph
    dsu_original = DSU(N)
    for u, v in edges:
        dsu_original.union(u, v)

    # Process queries
    output = []
    for _ in range(Q):
        x = int(data[idx])
        idx += 1
        y = int(data[idx])
        idx += 1
        if dsu_original.find(x) != dsu_original.find(y):
            output.append("No")
        else:
            if dsu_bridge.find(x) == dsu_bridge.find(y):
                output.append("Yes")
            else:
                output.append("No")
    
    print('\n'.join(output))

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