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

# 問題
https://atcoder.jp/contests/abc372/tasks/abc372_e

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

## Before
[AtCoder Beginner Contest 372_D 問題](https://qiita.com/o_chan_t/items/8013b43a5881420d8048)

## Next
[AtCoder Beginner Contest 373_C 問題](https://qiita.com/o_chan_t/items/e09143408dc986e34877)

## その他・記事まとめ
[Unity関連 / Qiita](https://qiita.com/o_chan_t/items/0b5ae1e7c45f106082b8)


# 解法手順1

## 1. Union-Find（素集合データ構造）の利用
- 頂点同士が連結されるたびに、それらを同じグループとして管理する。
- グループ管理にはUnion-Find（素集合データ構造）を使う。

## 2. 各グループ内で頂点番号を管理
- 各グループごとに、所属する頂点番号を降順でリストとして保持。
- マージ時には2つのグループのリストを結合し、降順ソートして上位10個だけ保持。

## 3. クエリ処理
- **タイプ1 (辺追加)**：
  - 頂点 $ u $ と頂点 $ v $ を連結。
  - Union-Findでそれぞれのrootを求め、異なる場合はマージ処理を行う。

- **タイプ2 (クエリ)**：
  - 頂点 $ v $ の属するグループについて、そのグループ内で頂点番号が大きい順に並べたときの $ k $ 番目の頂点番号を出力。
  - グループサイズが $ k $ 未満の場合は `-1` を出力。

## 処理フローまとめ
1. 入力受け取り (`io_func`)
   - 頂点数 $ N $、クエリ数 $ Q $、および各クエリ情報を取得。
2. 初期化 (`solve`)
   - Union-Find構造体 (`UnionFind`) を初期化。
3. クエリ処理 (`solve`内)
   - クエリタイプごとに以下の処理：
     - タイプ1：Union-Findでマージ処理。
     - タイプ2：該当するグループからk番目に大きい頂点番号または `-1` を出力。


# ACコード1
```python:ac.py

import logging

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)

    logger.debug(f"ロガーのセットアップが完了しました。デバッグモード: {debug_mode}")
    return logger

class UnionFind:
    def __init__(self, n, logger):
        self.par = [-1 for _ in range(n)]
        self.comp = [[i] for i in range(n)]
        self.logger = logger
        self.logger.debug(f"UnionFindを初期化しました。頂点数: {n}")

    def root(self, v):
        if self.par[v] < 0:
            return v
        else:
            self.par[v] = self.root(self.par[v])
            return self.par[v]

    def size(self, v):
        return -self.par[self.root(v)]

    def merge(self, u, v):
        u_root = self.root(u)
        v_root = self.root(v)
        if u_root == v_root:
            self.logger.debug(f"頂点{u}と頂点{v}は既に同じグループです。")
            return
        if self.size(u_root) > self.size(v_root):
            u_root, v_root = v_root, u_root

        # u_root を v_root にマージする
        self.comp[v_root] += self.comp[u_root]
        self.comp[u_root] = []
        self.comp[v_root].sort(reverse=True)
        self.comp[v_root] = self.comp[v_root][:10]

        # 親の更新処理
        self.par[v_root] += self.par[u_root]
        self.par[u_root] = v_root

        self.logger.debug(f"頂点{u}の属するグループを頂点{v}の属するグループにマージしました。")

def io_func():
    N, Q = map(int, input().split())
    queries = [list(map(int, input().split())) for _ in range(Q)]
    return N, Q, queries

def solve(N, Q, queries, logger):
    uf = UnionFind(N + 1, logger)
    for query in queries:
        if query[0] == 1:
            _, u, v = query
            uf.merge(u, v)
            logger.debug(f"クエリタイプ1: 頂点{u}と頂点{v}を接続しました。")
        else:
            _, v, k = query
            root_v = uf.root(v)
            comp_size = len(uf.comp[root_v])
            if comp_size < k:
                print(-1)
                logger.debug(f"クエリタイプ2: 頂点{v}の属するグループのサイズが{k}未満({comp_size})のため、-1を出力しました。")
            else:
                result = uf.comp[root_v][k - 1]
                print(result)
                logger.debug(f"クエリタイプ2: 頂点{v}の属するグループで{k}番目に大きい番号は{result}です。")

def main():
    debug_mode = False
    logger = setup_logger(debug_mode)
    N, Q, queries = io_func()
    solve(N, Q, queries, logger)

if __name__ == "__main__":
    main()


```