无名汉化组官网_什么是并查集

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

永无乡包含 n 座岛，编号从 1 到 n ，每座岛都有自己的独一无二的重要度，按照重要度可以将这 n 座岛排名，名次用 1 到 n 来表示。

某些岛之间由巨大的桥连接，通过桥可以从一个岛到达另一个岛。

如果从岛 a 出发经过若干座（含 0 座）桥可以到达岛 b ，则称岛 a 和岛 b 是连通的。

现在有两种操作：

B x y 表示在岛 x 与岛 y 之间修建一座新桥。
Q x k 表示询问当前与岛 x 连通的所有岛中第 k 重要的是哪座岛，即所有与岛 x 连通的岛中重要度排名第 k 小的岛是哪座，请你输出那个岛的编号。
输入格式
第一行是用空格隔开的两个正整数 n 和 m ，分别表示岛的个数以及一开始存在的桥数。

接下来的一行是用空格隔开的 n 个数，依次描述从岛 1 到岛 n 的重要度排名。

随后的 m 行每行是用空格隔开的两个正整数 ai 和 bi ，表示一开始就存在一座连接岛 ai 和岛 bi 的桥。

后面剩下的部分描述操作，该部分的第一行是一个正整数 q ，表示一共有 q 个操作，接下来的 q 行依次描述每个操作，操作的格式如上所述，以大写字母 Q 或 B 开始，后面跟两个不超过 n 的正整数，字母与数字以及两个数字之间用空格隔开。

输出格式
对于每个 Q x k 操作都要依次输出一行，其中包含一个整数，表示所询问岛屿的编号。

如果该岛屿不存在，则输出 −1。

数据范围
对于 20 的数据 n≤1000,q≤1000,
对于 100 的数据 n≤100000,m≤n,q≤300000

输入样例：
5 1
4 3 2 5 1
1 2
7
Q 3 2
Q 2 1
B 2 3
B 1 5
Q 2 1
Q 2 4
Q 2 3
输出样例：
-1
2
5
1
2

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 100;
struct Node{ 

int s[2],v,p;
int size,flag;
int id;
void init(int _v,int _p,int _id){ 

v = _v,p  = _p,id = _id;
size = 1;
}
}tr[N];
int root[N],ctx;
int w[N];
int f[N];
void pushup(int u){ 

tr[u].size = tr[tr[u].s[0]].size + tr[tr[u].s[1]].size + 1;
}
void pushdown(int u){ 

return;
}
void rotate(int x){ 

int y = tr[x].p,z = tr[y].p;
int k = tr[y].s[1] == x;
tr[z].s[tr[z].s[1] == y] = x,tr[x].p = z;
tr[y].s[k] = tr[x].s[k ^ 1],tr[tr[x].s[k ^ 1]].p = y;
tr[x].s[k ^ 1] = y,tr[y].p = x;
pushup(y);
pushup(x);
}
void splay(int x,int k,int r){ 

while(tr[x].p != k){ 

int y = tr[x].p,z = tr[y].p;
if(z != k){ 

if((tr[z].s[1] == y) ^ (tr[y].s[1] == x))rotate(x);
else rotate(y);
}
rotate(x);
}
if(!k)root[r] = x;
}
int Find(int x){ 

return f[x] = (x == f[x] ? f[x] : Find(f[x]));
}
int insert(int r,int v,int id){ 
        //r代表root[r]
int u = root[r],p = 0;
while(u)p = u,u = tr[u].s[v > tr[u].v];
u = ++ ctx;
if(p)tr[p].s[v > tr[p].v] = u;
tr[u].init(v,p,id);
splay(u,0,r);
return u;
}
int get_th(int k,int r){ 

int u = root[r];
while(u){ 
       
if(tr[tr[u].s[0]].size >= k)u = tr[u].s[0];
else if(tr[tr[u].s[0]].size + 1 == k)return tr[u].id;
else k -= tr[tr[u].s[0]].size + 1,u = tr[u].s[1];
}
return -1;
}
void dfs(int u,int b){ 

if(tr[u].s[0])dfs(tr[u].s[0],b);
if(tr[u].s[1])dfs(tr[u].s[1],b);
insert(b,tr[u].v,tr[u].id);
}
int main(){ 

int n,m;
cin>>n>>m;
int x,y;
for(int i = 1;i <= n;i ++){ 

cin>>x;
root[i] = f[i] = i;
tr[i].init(x,0,i);
}
ctx = n;
for(int i = 0;i < m;i ++){ 

cin>>x>>y;
int a = Find(x),b = Find(y);
if(a != b){ 

if(tr[root[a]].size > tr[root[b]].size)swap(a,b);//把a插入到b中
dfs(root[a],b);//合并
f[a] = b;
}
}
char c;
cin>>m;
for(int i = 0;i < m;i ++){ 

cin>>c>>x>>y;
if(c == 'Q'){ 

int r = Find(x);
if(y > tr[root[r]].size)cout<<-1<<endl;
else cout<<get_th(y,r)<<endl;
}
else { 

int a = Find(x),b = Find(y);
if(a != b){ 

if(tr[root[a]].size > tr[root[b]].size)swap(a,b);//把a插入到b中
dfs(root[a],b);//合并
f[a] = b;
}
}
}
return 0;
}

2. 每一次合并不创建新节点

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
struct Node{ 

int s[2],v,p;
int size,flag;
int id;
void init(int _v,int _p,int _id){ 

v = _v,p  = _p,id = _id;
size = 1;
}
}tr[N];
int root[N],ctx;
int w[N];
int f[N];
void pushup(int u){ 

tr[u].size = tr[tr[u].s[0]].size + tr[tr[u].s[1]].size + 1;
}
void pushdown(int u){ 

return;
}
void rotate(int x){ 

int y = tr[x].p,z = tr[y].p;
int k = tr[y].s[1] == x;
tr[z].s[tr[z].s[1] == y] = x,tr[x].p = z;
tr[y].s[k] = tr[x].s[k ^ 1],tr[tr[x].s[k ^ 1]].p = y;
tr[x].s[k ^ 1] = y,tr[y].p = x;
pushup(y);
pushup(x);
}
void splay(int x,int k,int r){ 

while(tr[x].p != k){ 

int y = tr[x].p,z = tr[y].p;
if(z != k){ 

if((tr[z].s[1] == y) ^ (tr[y].s[1] == x))rotate(x);
else rotate(y);
}
rotate(x);
}
if(!k)root[r] = x;
}
int Find(int x){ 

return f[x] = (x == f[x] ? f[x] : Find(f[x]));
}
int insert(int r,int x){ 
        //r代表root[r]
int u = root[r],p = 0;
while(u)p = u,u = tr[u].s[tr[x].v > tr[u].v];
if(p)tr[p].s[tr[x].v > tr[p].v] = x;
tr[x].p = p;
splay(x,0,r);
return u;
}
int get_th(int k,int r){ 

int u = root[r];
while(u){ 
       
if(tr[tr[u].s[0]].size >= k)u = tr[u].s[0];
else if(tr[tr[u].s[0]].size + 1 == k)return tr[u].id;
else k -= tr[tr[u].s[0]].size + 1,u = tr[u].s[1];
}
return -1;
}
void dfs(int u,int b){ 

if(tr[u].s[0])dfs(tr[u].s[0],b);
if(tr[u].s[1])dfs(tr[u].s[1],b);
insert(b,u);
}
int main(){ 

int n,m;
cin>>n>>m;
int x,y;
for(int i = 1;i <= n;i ++){ 

scanf("%d",&x);
root[i] = f[i] = i;
tr[i].init(x,0,i);
}
ctx = n;
for(int i = 0;i < m;i ++){ 

scanf("%d %d",&x,&y);
int a = Find(x),b = Find(y);
if(a != b){ 

if(tr[root[a]].size > tr[root[b]].size)swap(a,b);//把a插入到b中
dfs(root[a],b);//合并
f[a] = b;
}
}
char c;
cin>>m;
for(int i = 0;i < m;i ++){ 

cin>>c>>x>>y;
if(c == 'Q'){ 

int r = Find(x);
if(y > tr[root[r]].size)printf("-1\n");
else printf("%d\n",get_th(y,r));
}
else { 

int a = Find(x),b = Find(y);
if(a != b){ 

if(tr[root[a]].size > tr[root[b]].size)swap(a,b);//把a插入到b中
dfs(root[a],b);//合并
f[a] = b;
}
}
}
return 0;
}