CF1416D Graph and Queries

给定一个无向图，包含 $n$ 个顶点和 $m$ 条边。最初，每个顶点上写有一个整数：顶点 $i$ 上写有 $p_i$。所有 $p_i$ 是 $1$ 到 $n$ 的互不相同的整数。 你需要处理 $q$ 个两种类型的操作： - $1\ v$ ——在所有通过图中的边从顶点 $v$ 可达的顶点中（包括 $v$ 本身），找到一个顶点 $u$，使得 $u$ 上写的数 $p_u$ 最大，输出 $p_u$，并将 $p_u$ 变为 $0$； - $2\ i$ ——删除图中的第 $i$ 条边。 注意，在第一种操作中，可能所有从 $v$ 可达的顶点上都写着 $0$。在这种情况下，$u$ 没有明确的定义，但由于选择 $u$ 不影响结果，你可以任选一个从 $v$ 可达的顶点并输出其值（即 $0$）。

第一行包含三个整数 $n$、$m$ 和 $q$（$1 \le n \le 2 \cdot 10^5$；$1 \le m \le 3 \cdot 10^5$；$1 \le q \le 5 \cdot 10^5$）。 第二行包含 $n$ 个互不相同的整数 $p_1, p_2, \ldots, p_n$，其中 $p_i$ 表示初始写在顶点 $i$ 上的数（$1 \le p_i \le n$）。 接下来 $m$ 行，每行包含两个整数 $a_i$ 和 $b_i$（$1 \le a_i, b_i \le n$，$a_i \ne b_i$），表示第 $i$ 条边连接顶点 $a_i$ 和 $b_i$。保证图中没有重边。 接下来 $q$ 行，每行描述一个操作，格式如下： - $1\ v$ ——表示第一种操作，查询顶点 $v$（$1 \le v \le n$）。 - $2\ i$ ——表示第二种操作，删除第 $i$ 条边（$1 \le i \le m$）。对于每个第二种操作，保证对应的边尚未被删除。

对于每个第一种操作，输出所选顶点 $u$ 上写的值 $p_u$。

由 ChatGPT 4.1 翻译