結果

問題 No.3200 Sinking Islands
ユーザー YY-otter
提出日時 2025-07-03 16:47:22
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 527 ms / 2,000 ms
コード長 3,740 bytes
コンパイル時間 357 ms
コンパイル使用メモリ 82,152 KB
実行使用メモリ 106,108 KB
最終ジャッジ日時 2025-07-03 16:52:04
合計ジャッジ時間 11,098 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

# f.py
import sys

class DSU:
    """
    DSU (Disjoint Set Union) または Union-Find データ構造。
    経路圧縮 (Path Compression) とサイズによる結合 (Union by Size) を実装しています。
    """
    def __init__(self, n: int):
        """
        Args:
            n (int): 要素の数。0からnまでのn+1個の要素を初期化します。
        """
        # 各要素の親を格納するリスト。最初は自身が親。
        self.parent = list(range(n + 1))
        # 各集合のサイズを格納するリスト
        self.sz = [1] * (n + 1)

    def find(self, i: int) -> int:
        """
        要素iが属する集合の代表元（ルート）を探します。
        経路圧縮を行い、計算量を削減します。

        Args:
            i (int): 探す対象の要素。

        Returns:
            int: 要素iが属する集合の代表元。
        """
        if self.parent[i] == i:
            return i
        self.parent[i] = self.find(self.parent[i])
        return self.parent[i]

    def unite(self, i: int, j: int):
        """
        要素iが属する集合と要素jが属する集合を併合します。
        サイズが小さい方の木を大きい方の木に結合します（Union by Size）。

        Args:
            i (int): 併合する要素1。
            j (int): 併合する要素2。
        """
        root_i = self.find(i)
        root_j = self.find(j)
        if root_i != root_j:
            if self.sz[root_i] < self.sz[root_j]:
                root_i, root_j = root_j, root_i
            self.parent[root_j] = root_i
            self.sz[root_i] += self.sz[root_j]

def f_solver():
    """
    メインの処理。
    """
    # 高速入出力
    input = sys.stdin.readline

    N, M = map(int, input().split())
    edges = [tuple(map(int, input().split())) for _ in range(M)]

    Q = int(input())
    # クエリで指定された辺のインデックスを0-indexedで読み込む
    query_edges = [int(input()) - 1 for _ in range(Q)]

    # クエリで削除される辺をマーク
    is_removed = [False] * M
    for edge_idx in query_edges:
        is_removed[edge_idx] = True

    # DSUをN個の頂点で初期化
    dsu = DSU(N)
    # クエリで削除されない辺を使って、初期の連結成分を構築
    for i in range(M):
        if not is_removed[i]:
            u, v = edges[i]
            dsu.unite(u, v)

    # 初期の非連結ペアの数を計算
    current_disconnected_pairs = 0
    visited_root = [False] * (N + 1)
    connected_nodes = 0
    for i in range(1, N + 1):
        root = dsu.find(i)
        if not visited_root[root]:
            size = dsu.sz[root]
            # 現在の連結成分のノードと、まだ訪れていないノードとのペア数を加算
            current_disconnected_pairs += size * (N - connected_nodes - size)
            connected_nodes += size
            visited_root[root] = True

    # クエリを逆順に処理（削除された辺を元に戻していく）
    ans = [0] * Q
    for i in range(Q - 1, -1, -1):
        ans[i] = current_disconnected_pairs
        
        edge_idx = query_edges[i]
        u, v = edges[edge_idx]
        root_u = dsu.find(u)
        root_v = dsu.find(v)

        # 辺を追加することで異なる連結成分が1つになる場合、
        # 非連結ペアの数は (成分uのサイズ * 成分vのサイズ) だけ減少する
        if root_u != root_v:
            current_disconnected_pairs -= dsu.sz[root_u] * dsu.sz[root_v]
        
        dsu.unite(u, v)

    # 答えをまとめて出力
    for val in ans:
        print(val)

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