MT3055 交换排列

1.思路 

若数对为（1，4）和（4，7），则说明14可以互换，47可以互换，并且17也可以互换。所以把可以交换的元素放到一个集合中。

例如样例1：有三个集合，分别为147，369，258。排列中第一个元素为1，所以在147中找最大的数7输出；排列中第二个元素为2，所以在258中找最大的数8输出。（寻找最大值用大根堆存储）

2.代码

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n, m;
int num[N], fa[N];
priority_queue<int> q[N];
int find(int x)
{ // 查找，带路径压缩return x == fa[x] ? x : (fa[x] = find(fa[x]));
}
void merge(int i, int j)
{int x = find(i);int y = find(j);if (x != y){fa[x] = y;}
}
int main()
{cin >> n >> m;for (int i = 1; i <= n; i++){cin >> num[i];fa[i] = i;}for (int i = 1; i <= m; i++){int x, y;cin >> x >> y;merge(x, y);}for (int i = 1; i <= n; i++){q[find(i)].push(num[i]);}for (int i = 1; i <= n; i++){ // 每次取集合中最大的元素int a = find(i);cout << q[a].top() << " ";q[a].pop();}return 0;
}