题目描述

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

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

思路分析

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

1. 关键点

   • 操作数量 q、节点数 n 都可达 10^5，因此每个操作的时间复杂度需要尽量低。
   • 查询操作仅要求输出第 k 大的邻居，其中 k 最大为 10，即只关心每个节点最大的 10 个邻居（编号最大者）。

2. 数据结构选择

   • 对于去重判断，我们需要为每个节点维护一个集合（如 unordered_set/HashSet）存储所有已经添加的邻居。
   • 对于查询操作，由于 k ≤ 10，我们只需要为每个节点维护一个大小最多为 10 的列表（数组、ArrayList 等），存储“前10大”的邻居，保证每次查询时能直接取到第 k 大。
   • 当新边加入时，如果新邻居的编号比当前“前10大”中最小的还大，就可以将其插入并删除列表中最小的元素（若列表大小超过 10）。

3. 算法流程

   • 添加边：
     • 检查两个节点间是否已有边（通过集合去重）；
     • 若无，则在两个节点的集合中添加对方；
     • 对于每个节点，更新其维护的前10邻居列表（如果列表未满 10，直接加入并排序；如果已满且新节点大于列表中最小的，则插入后剔除最小元素）。
   • 查询：
     • 直接查看对应节点维护的列表大小，如果不足 k 个则返回 -1，否则列表升序存储，则第 k 大邻居为列表中索引为 size - k 的元素。

代码实现

C++ 解法

#include <iostream>
#include <vector>
#include <unordered_set>
#include <algorithm>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, q;
    cin >> n >> q;
    
    // neighbors[i] 存储节点 i 的所有邻居（用于判断是否重复添加）
    vector<unordered_set<int>> neighbors(n+1);
    // top10[i] 存储节点 i 的前10大邻居，按升序排列（方便获取倒数第 k 个即第 k 大）
    vector<vector<int>> top10(n+1);
    
    while(q--){
        int type;
        cin >> type;
        if(type == 1){
            int u, v;
            cin >> u >> v;
            // 若 u 与 v 已经连接，则跳过
            if(neighbors[u].count(v)) continue;
            // 无向图，双向添加
            neighbors[u].insert(v);
            neighbors[v].insert(u);
            
            // 更新节点 u 的 top10 列表
            if(top10[u].size() < 10){
                top10[u].push_back(v);
                sort(top10[u].begin(), top10[u].end());
            } else if(v > top10[u][0]){
                top10[u].push_back(v);
                sort(top10[u].begin(), top10[u].end());
                // 保持列表大小为10，删除最小的元素
                if(top10[u].size() > 10) top10[u].erase(top10[u].begin());
            }
            
            // 同理更新节点 v 的 top10 列表
            if(top10[v].size() < 10){
                top10[v].push_back(u);
                sort(top10[v].begin(), top10[v].end());
            } else if(u > top10[v][0]){
                top10[v].push_back(u);
                sort(top10[v].begin(), top10[v].end());
                if(top10[v].size() > 10) top10[v].erase(top10[v].begin());
            }
        } else if(type == 2){
            int u, k;
            cin >> u >> k;
            int sz = top10[u].size();
            if(k > sz) {
                cout << -1 << "\n";
            } else {
                // top10[u] 升序排列，第 k 大即为索引 sz - k 的元素
                cout << top10[u][sz - k] << "\n";
            }
        }
    }
    return 0;
}

Python 解法

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import sys

def main():
    # 使用 sys.stdin.readline 加速输入
    input = sys.stdin.readline
    n, q = map(int, input().split())
    # neighbors[i] 存储节点 i 的所有邻居，用于去重
    neighbors = [set() for _ in range(n+1)]
    # top10[i] 存储节点 i 的前10大邻居（升序排列）
    top10 = [[] for _ in range(n+1)]
    res = []
    
    for _ in range(q):
        op = list(map(int, input().split()))
        if op[0] == 1:
            u, v = op[1], op[2]
            # 如果已经存在边则跳过
            if v in neighbors[u]:
                continue
            neighbors[u].add(v)
            neighbors[v].add(u)
            
            # 更新节点 u 的 top10 列表
            if len(top10[u]) < 10:
                top10[u].append(v)
                top10[u].sort()
            elif v > top10[u][0]:
                top10[u].append(v)
                top10[u].sort()
                if len(top10[u]) > 10:
                    top10[u].pop(0)  # 删除最小值
            
            # 更新节点 v 的 top10 列表
            if len(top10[v]) < 10:
                top10[v].append(u)
                top10[v].sort()
            elif u > top10[v][0]:
                top10[v].append(u)
                top10[v].sort()
                if len(top10[v]) > 10:
                    top10[v].pop(0)
        else:
            u, k = op[1], op[2]
            if k > len(top10[u]):
                res.append("-1")
            else:
                # 第 k 大即为列表中索引 len(top10[u]) - k 的元素
                res.append(str(top10[u][len(top10[u]) - k]))
    
    sys.stdout.write("\n".join(res))

if __name__ == '__main__':
    main()

Java 解法

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException{
        // 使用 BufferedReader 加速输入
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] firstLine = br.readLine().split(" ");
        int n = Integer.parseInt(firstLine[0]);
        int q = Integer.parseInt(firstLine[1]);
        
        // neighbors[i] 存储节点 i 的所有邻居（用于判断是否重复添加）
        HashSet<Integer>[] neighbors = new HashSet[n+1];
        // top10[i] 存储节点 i 的前10大邻居（使用 ArrayList 存储，保持升序）
        ArrayList<Integer>[] top10 = new ArrayList[n+1];
        for (int i = 1; i <= n; i++){
            neighbors[i] = new HashSet<>();
            top10[i] = new ArrayList<>();
        }
        
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < q; i++){
            String line = br.readLine();
            String[] parts = line.split(" ");
            int type = Integer.parseInt(parts[0]);
            if (type == 1) {
                int u = Integer.parseInt(parts[1]);
                int v = Integer.parseInt(parts[2]);
                // 如果 u 与 v 已经连接则跳过
                if (neighbors[u].contains(v)) continue;
                neighbors[u].add(v);
                neighbors[v].add(u);
                // 更新节点 u 的 top10 列表
                updateTop10(top10[u], v);
                // 更新节点 v 的 top10 列表
                updateTop10(top10[v], u);
            } else if (type == 2) {
                int u = Integer.parseInt(parts[1]);
                int k = Integer.parseInt(parts[2]);
                // 先对 top10 列表排序（若更新时已排序，可省略此步，但这里简单处理）
                Collections.sort(top10[u]);
                int size = top10[u].size();
                if (k > size) {
                    sb.append("-1\n");
                } else {
                    // 第 k 大即为列表中索引 size - k 的元素
                    sb.append(top10[u].get(size - k)).append("\n");
                }
            }
        }
        System.out.print(sb.toString());
    }
    
    // 辅助方法：更新节点的 top10 邻居列表
    private static void updateTop10(ArrayList<Integer> list, int val) {
        if (list.size() < 10) {
            list.add(val);
            Collections.sort(list);
        } else {
            Collections.sort(list);
            // 若新值大于列表中最小的值，则将其加入，并移除最小的元素以保持大小为10
            if (val > list.get(0)) {
                list.add(val);
                Collections.sort(list);
                list.remove(0);
            }
        }
    }
}

题目内容

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

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

输入描述

第一行包含两个整数$n$和$q$，分别表示节点的数量和操作的数量$(1≤n≤10^5,1≤q≤10^5)$。

接下来的q行中，每行包含一个操作:

对于连接操作，格式为1 u v，其中$1≤u,v≤n$，如果原本两点之间有边，则忽略这次操作。

对于查询操作，格式为2 u k，其中$1≤u≤n,1≤k≤10$。

输出描述

对于每个查询操作，输出一行结果，表示编号第$k$大的边的目标节点。如果不存在这样的边，则输出$-1$。

样例1

输入

5 8
1 1 2
1 1 3
1 2 3
2 1 1
2 1 2
1 2 4
2 2 1
2 2 7

输出

3
2
4 
-1

说明

• 操作$1$:112连接节点$1$和$2$。
• 操作$2$:113连接节点$1$和$3$。 `
• 操作$3$:123 连接节点$2$和 $3$。
• 操作$4$:211查询节点$1$直接相连的相邻节点中，编号第$1$大的是$3$(相连节点为$2,3$，按编号排序)。
• 操作$5$:212查询节点$1$直接相连的相邻节点中，编号第$2$大的是$2$(相连节点为$2,3$)。
• 操作$6$:124 连接节点$2$和$4$。
• 操作$7$:221查询节点$2$直接相连的相邻节点中，编号第$1$大的是$4$(相连节点为$1,3,4$)。
• 操作$8$:227查询节点$2$直接相连的相邻节点中，编号第$7$大的是$-1$(只存在$3$个相邻节点)。