AT_abc372_e [ABC372E] K-th Largest Connected Components

题目描述

有一个包含 $N$ 个顶点、$0$ 条边的无向图。顶点编号为 $1$ 到 $N$。

给定 $Q$ 个查询，请按给定顺序依次处理。每个查询有以下两种类型之一：

• 类型 $1$：以 1 u v 的形式给出。在顶点 $u$ 和顶点 $v$ 之间添加一条边。
• 类型 $2$：以 2 v k 的形式给出。在与顶点 $v$ 连通的所有顶点中，输出编号第 $k$ 大的顶点编号。如果与顶点 $v$ 连通的顶点不足 $k$ 个，则输出 -1。

输入格式

输入以如下格式从标准输入读入。

$N$ $Q$
$\mathrm{query}_1$
$\mathrm{query}_2$
$\vdots$
$\mathrm{query}_Q$

其中，$\mathrm{query}_i$ 表示第 $i$ 个查询，格式如下之一：

$1$ $u$ $v$

$2$ $v$ $k$

输出格式

设类型 $2$ 的查询有 $q$ 个，请输出 $q$ 行。第 $i$ 行输出第 $i$ 个类型 $2$ 查询的答案。

输入输出样例 #1

输入 #1

4 10
1 1 2
2 1 1
2 1 2
2 1 3
1 1 3
1 2 3
1 3 4
2 1 1
2 1 3
2 1 5

输出 #1

2
1
-1
4
2
-1

输入输出样例 #2

输入 #2

6 20
1 3 4
1 3 5
2 1 1
2 3 1
1 1 5
2 6 9
2 1 3
2 6 1
1 4 6
2 2 1
2 6 2
2 4 7
1 1 4
2 6 2
2 3 4
1 2 5
2 4 1
1 1 6
2 3 3
2 1 3

输出 #2

1
5
-1
3
6
2
5
-1
5
3
6
4
4

说明/提示

数据范围

• $1 \leq N, Q \leq 2 \times 10^5$
• 对于类型 $1$ 的查询，$1 \leq u < v \leq N$
• 对于类型 $2$ 的查询，$1 \leq v \leq N,\ 1 \leq k \leq 10$
• 所有输入均为整数

样例解释 1

• 第 $1$ 个查询，在顶点 $1$ 和顶点 $2$ 之间添加一条边。
• 第 $2$ 个查询，与顶点 $1$ 连通的顶点有 $1,2$ 共 $2$ 个。在这些顶点中，第 $1$ 大的是 $2$，输出 $2$。
• 第 $3$ 个查询，与顶点 $1$ 连通的顶点有 $1,2$ 共 $2$ 个。在这些顶点中，第 $2$ 大的是 $1$，输出 $1$。
• 第 $4$ 个查询，与顶点 $1$ 连通的顶点有 $1,2$ 共 $2$ 个，不足 $3$ 个，输出 -1。
• 第 $5$ 个查询，在顶点 $1$ 和顶点 $3$ 之间添加一条边。
• 第 $6$ 个查询，在顶点 $2$ 和顶点 $3$ 之间添加一条边。
• 第 $7$ 个查询，在顶点 $3$ 和顶点 $4$ 之间添加一条边。
• 第 $8$ 个查询，与顶点 $1$ 连通的顶点有 $1,2,3,4$ 共 $4$ 个。在这些顶点中，第 $1$ 大的是 $4$，输出 $4$。
• 第 $9$ 个查询，与顶点 $1$ 连通的顶点有 $1,2,3,4$ 共 $4$ 个。在这些顶点中，第 $3$ 大的是 $2$，输出 $2$。
• 第 $10$ 个查询，与顶点 $1$ 连通的顶点有 $1,2,3,4$ 共 $4$ 个，不足 $5$ 个，输出 -1。

由 ChatGPT 4.1 翻译