# 2. 题解

MMP 明天期末考啊

## 做法 1

#include <bits/stdc++.h>
#define NS (100005)
using namespace std;
typedef pair<int,int> PII;
template<typename _Tp>inline void IN(_Tp&dig)
{
char c;dig=0;
while(c=getchar(),!isdigit(c));
while(isdigit(c))dig=dig*10+c-'0',c=getchar();
}
int n,m,fa[NS];
bool book[NS];
priority_queue<PII,vector<PII>,greater<PII> > pq[NS];
int findf(int a){return fa[a]==a?a:fa[a]=findf(fa[a]);}
int main()
{
IN(n),IN(m);
for(int i=1,j;i<=n;i++)IN(j),pq[i].push((PII){j,i}),fa[i]=i;
for(int i=1,a,b,c;i<=m;i++)
if(IN(a),IN(b),a==1)
{
if(IN(c),book[b]||book[c])continue;
b=findf(b),c=findf(c);
if(b==c)continue;
if(pq[b].size()>pq[c].size())swap(b,c);
while(!pq[b].empty())
{
pq[c].push(pq[b].top());
fa[pq[b].top().second]=c;
pq[b].pop();
}
}
else
{
if(book[b]){puts("-1");continue;}
b=findf(b),printf("%d\n",pq[b].top().first);
book[pq[b].top().second]=1,pq[b].pop();
}
return 0;
}


## 做法 2

#include <bits/stdc++.h>

#define NS 100005

using namespace std;

typedef pair<int, int> PII;

struct node {
PII k;
int l, r, dis;
} e[NS];

int n, m, f[NS], rt[NS];
bool rm[NS];

int findf(int a) {
return f[a] == a ? a : f[a] = findf(f[a]);
}

int merge(int a, int b) {
if ((!a) || (!b)) return a | b;
if (e[a].k > e[b].k) swap(a, b);
e[a].r = merge(e[a].r, b);
if (e[e[a].l].dis < e[e[a].r].dis) swap(e[a].l, e[a].r);
e[a].dis = e[e[a].r].dis + 1;
return a;
}

int main(int argc, char const* argv[]) {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i += 1) {
scanf("%d", &e[i].k.first);
e[i].k.second = i, rt[i] = f[i] = i;
}
while (m--) {
int t, x, y;
scanf("%d%d", &t, &x);
if (t == 1) {
scanf("%d", &y);
if (rm[x] || rm[y]) continue;
x = findf(x), y = findf(y);
if (x != y) rt[x] = merge(rt[x], rt[y]), f[y] = x;
}
else {
if (rm[x]) puts("-1");
else {
x = findf(x);
printf("%d\n", e[rt[x]].k.first);
rm[e[rt[x]].k.second] = true;
rt[x] = merge(e[rt[x]].l, e[rt[x]].r);
}
}
}
return 0;
}