题目内容

给定一张初始没有边的无向图，图的节点编号为$1$到$n$。你可以进行两种操作: 连接操作:

• 连接两个节点$u$和$v$，表示在它们之间添加一条边。
• 查询操作:询问节点$u$直接相连的点中，编号第$k$大的相邻节点是什么。若直接相邻的点不足$k$个，则返回$-1$。

题目描述

给定一张初始没有边的无向图，节点编号为 1 到 n。图支持两种操作：

• 连接操作：格式为 1 u v，表示在节点 u 和节点 v 之间添加一条边（若该边已存在，则忽略）。
• 查询操作：格式为 2 u k，询问节点 u 的所有直接相邻节点中，编号第 k 大的节点是多少（相邻节点按节点编号升序排列，则第 k 大即为倒数第 k 个）。若 u 的相邻节点不足 k 个，则输出 -1。

思路分析

本题要求在动态添加边的无向图中，实现高效的邻居查询操作。由于每个查询只关心第 k 大的邻居且 k 最大为 10，我们可以为每个节点维护一个大小不超过 10的有序列表，记录其编号最大的邻居。在添加边时，先通过集合判断是否重复，然后更新该节点的局部最大邻居列表；查询时直接从有序列表中获取答案。这样既能确保添加边和查询操作的时间复杂度低，又能满足题目要求。