【競技プログラミング】AtCoder Beginner Contest 264_E問題

# 問題
https://atcoder.jp/contests/abc264/tasks/abc264_e

# 既存投稿一覧ページへのリンク
[一覧ページ](https://qiita.com/o_chan_t/items/fc759695acfaef8df2cc)


# 解法手順1
1. Union-Find木を初期化します。都市とは別に、全ての発電所を代表する仮想的なノードを1つ追加する。

2. クエリで切断されない電線について、Union-Find木で接続する。

3. クエリを逆順に処理する。
   - 現在の状態で、発電所を代表するノードに接続されている都市の数を数えます。これが答えとなる。
   - クエリで指定された電線を接続する（逆順なので、本来は切断する操作）。

4. 全てのクエリの結果を出力する。

## 入力例01の可視化
1. 初期状態
![2501252017.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/530912/dc4fd202-5540-f25f-ec0f-01a170e70ec2.png)


2. 3番目の(5-10)の経路が遮断され、都市5が停電
![2501252018.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/530912/77c62a6e-f135-8056-d3cd-1722a3b28682.png)


3. 5番目と8番目の(2-9)、(3-6)の経路が遮断され、都市2、都市3が停電
![2501252019.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/530912/a4cb1910-8f37-b220-4fbe-d0d1c880df82.png)

4. 10番目と2番目と7番目の(1-8)、(4-10)、(1-7)の経路が遮断され、都市1が停電
![2501252020.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/530912/22351d83-a315-4f00-3f74-59a0936aa526.png)



# ACコード1
```python:ac.py
class UnionFind:
    def __init__(self, n):
        self.par = [-1] * n  # 親ノードを格納するリスト。初期値は全て-1（自身が根）
    
    def root(self, x):
        if self.par[x] < 0:  # xが根の場合
            return x
        self.par[x] = self.root(self.par[x])  # 経路圧縮
        return self.par[x]
    
    def unite(self, x, y):
        rx, ry = self.root(x), self.root(y)  # xとyの根を取得
        
        if rx == ry:  # 既に同じ木に属している場合
            return
        
        if -self.par[rx] < -self.par[ry]:  # ryの方が大きい木の場合
            rx, ry = ry, rx
        
        self.par[rx] += self.par[ry]  # rxにryを統合
        self.par[ry] = rx
    
    def size(self, x):
        return -self.par[self.root(x)]  # xが属する木のサイズを返す

def io_func():
    N, _, E = map(int, input().split())  # 都市数、発電所数、電線数を入力
    edges = [tuple(map(lambda x: min(N, int(x) - 1), input().split())) for _ in range(E)]  # 電線の情報を入力
    Q = int(input())  # クエリ数を入力
    query = [int(input()) - 1 for _ in range(Q)]  # クエリを入力
    return N, E, edges, Q, query

def solve(N, E, edges, Q, query):
    ans = [0] * Q  # 答えを格納するリスト
    uf = UnionFind(N + 1)  # Union-Find木を初期化（都市 + 仮想ノード）
    
    for i in set(range(E)) - set(query):  # クエリで切断されない電線を接続
        u, v = edges[i]
        uf.unite(u, v)
    
    for i in range(Q - 1, -1, -1):  # クエリを逆順に処理
        ans[i] = uf.size(N) - 1  # 発電所（仮想ノード）に接続されている都市数を計算
        uf.unite(*edges[query[i]])  # クエリで指定された電線を接続
    
    for res in ans:  # 結果を出力
        print(res)

# メイン処理
N, E, edges, Q, query = io_func()  # 入力を受け取る
solve(N, E, edges, Q, query)  # 問題を解く

###
# N: 都市の数
# E: 電線の数
# edges: 電線の接続情報を格納するリスト
# Q: クエリの数
# query: クエリの情報を格納するリスト
# ans: 各クエリに対する答えを格納するリスト
# uf: Union-Find木のインスタンス

# 1. UnionFind クラス:
#    - __init__: Union-Find木を初期化
#    - root: 要素の根を見つける（経路圧縮あり）
#    - unite: 2つの要素を結合
#    - size: 指定された要素が属する木のサイズを返す
# 2. io_func 関数:
#    - 標準入力から問題の入力を受け取り、必要なデータ構造に変換
# 3. solve 関数:
#    - Union-Find木を用いて問題を解く
#    - クエリを逆順に処理し、各時点での電気の通っている都市数を計算
#    - 結果を出力
# 4. メイン処理:
#    - io_func で入力を受け取り
#    - solve 関数を呼び出して問題を解く

```
## オブジェクト指向版1(TLE)
```python:ac_object.py
import logging
from abc import ABC, abstractmethod

def setup_logger(debug_mode):
    logger = logging.getLogger(__name__)
    if not logger.handlers:  # ハンドラが存在しない場合のみ追加
        logger.setLevel(logging.DEBUG if debug_mode else logging.INFO)
        formatter = logging.Formatter('%(asctime)s - %(name)s - %(levelname)s - %(message)s')
        
        file_handler = logging.FileHandler('program_trace.log', encoding="utf8")
        file_handler.setFormatter(formatter)
        logger.addHandler(file_handler)
    
    return logger

class UnionFind:
    def __init__(self, n, debug_mode=False):
        self.par = [-1] * n  # 親ノードを格納するリスト。初期値は全て-1（自身が根）
        self.logger = setup_logger(debug_mode)

    def root(self, x):
        if self.par[x] < 0:  # xが根の場合
            self.logger.debug(f"ノード {x} は根です")
            return x
        self.logger.debug(f"ノード {x} の親を探索中")
        self.par[x] = self.root(self.par[x])  # 経路圧縮
        self.logger.debug(f"ノード {x} の根は {self.par[x]} です")
        return self.par[x]

    def unite(self, x, y):
        self.logger.debug(f"ノード {x} と {y} を結合します")
        rx, ry = self.root(x), self.root(y)  # xとyの根を取得
        
        if rx == ry:  # 既に同じ木に属している場合
            self.logger.debug(f"ノード {x} と {y} は既に同じ木に属しています")
            return
        
        if -self.par[rx] < -self.par[ry]:  # ryの方が大きい木の場合
            rx, ry = ry, rx
        
        self.par[rx] += self.par[ry]  # rxにryを統合
        self.par[ry] = rx
        self.logger.debug(f"ノード {x} と {y} を結合しました。新しい根は {rx} です")

    def size(self, x):
        size = -self.par[self.root(x)]  # xが属する木のサイズを返す
        self.logger.debug(f"ノード {x} が属する木のサイズは {size} です")
        return size

class InputHandler(ABC):
    @abstractmethod
    def get_input(self):
        pass

class StandardInputHandler(InputHandler):
    def get_input(self):
        N, _, E = map(int, input().split())  # 都市数、発電所数、電線数を入力
        # edges = [tuple(map(lambda x: min(N, int(x) - 1), input().split())) for _ in range(E)] # 電線の情報を入力
        edges = []
        for _ in range(E):
            u, v = input().split()
            u = min(N, int(u) - 1)
            v = min(N, int(v) - 1)
            edges.append((u, v))
        Q = int(input())  # クエリ数を入力
        query = [int(input()) - 1 for _ in range(Q)]  # クエリを入力
        return N, E, edges, Q, query

class OutputHandler(ABC):
    @abstractmethod
    def output_result(self, result):
        pass

class StandardOutputHandler(OutputHandler):
    def output_result(self, result):
        for res in result:
            print(res)

class ElectricityProblemSolver:
    def __init__(self, input_handler: InputHandler, output_handler: OutputHandler, debug_mode=False):
        self.input_handler = input_handler
        self.output_handler = output_handler
        self.debug_mode = debug_mode
        self.logger = setup_logger(debug_mode)

    def solve(self):
        # 入力を受け取る
        N, E, edges, Q, query = self.input_handler.get_input()
        self.logger.debug(f"入力: N={N}, E={E}, Q={Q}")
        self.logger.debug(f"入力: edges={edges}")
        self.logger.debug(f"入力: query={query}")
        
        # 問題を解く
        ans = [0] * Q  # 答えを格納するリスト
        uf = UnionFind(N + 1, self.debug_mode)  # Union-Find木を初期化（都市 + 仮想ノード）
        
        self.logger.debug("クエリで切断されない電線を接続")
        for i in set(range(E)) - set(query):  # クエリで切断されない電線を接続
            u, v = edges[i]
            uf.unite(u, v)
        
        self.logger.debug("クエリを逆順に処理")
        for i in range(Q - 1, -1, -1):  # クエリを逆順に処理
            ans[i] = uf.size(N) - 1  # 発電所（仮想ノード）に接続されている都市数を計算
            self.logger.debug(f"クエリ {Q-i}: 接続都市数 = {ans[i]}")
            uf.unite(*edges[query[i]])  # クエリで指定された電線を接続
        
        # 結果を出力
        self.logger.debug("結果を出力")
        self.output_handler.output_result(ans)

# メイン処理
if __name__ == "__main__":
    input_handler = StandardInputHandler()
    output_handler = StandardOutputHandler()
    solver = ElectricityProblemSolver(input_handler, output_handler, debug_mode=True)
    solver.solve()
```

### オブジェクト図
![2025年01月24日20時19分_atcoder264E.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/530912/1f127039-ca71-0711-d771-6279bbbe9db3.png)