大佬求条!救救孩子吧！😭

常规
1

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 翻译

样例没过

#include<bits/stdc++.h>
using namespace std;
const int MAX_N=1e5*2+10;
set<int> s[MAX_N];
int n,t,d[MAX_N];
int found(int x){return (x==d[x])?x:d[x]=found(d[x]);}
int main(){
	cin>>n>>t;
	for(int i=1;i<=n;i++){
		s[i].insert(i);
		d[i]=i;
	}
	while(t--){
		int a,b,c;
		cin>>a>>b>>c;
		b=found(b);
        if(s[b].size()<s[c].size())swap(b,c);
		if(a==1){
			c=found(c);
			s[b].insert(c);
			s[c].insert(b);
			if(b!=c){
				d[c]=b;
				for(auto i:s[c])s[b].insert(i);
			}
			continue;
		}
		if(c>s[b].size()){
			cout<<-1<<endl;
			continue;
		}
		auto now=s[b].end();
		for(int i=1;i<=c;i++,now--)cout<<*now<<endl; 
	}
	return 0;
}
1 个赞