0特殊的数字排序 - 蓝桥云课
问题描述
小明被挑选去参加一个ACM比赛。他的任务是解决一个很特别的问题：给定一个整数数组，但是只能通过交换任意两个数的方式来排序。听起来很简单对吗？但是这个问题的难点在于，只有某些数字是可以交换的。例如，数字7和数字3可以交换，但是数字5可能不能和任何数字交换。
你的任务是，给定一个整数数组和一个允许交换的数字对列表，找到可能的最大排序数组。
例如，如果我们有一个数组[2, 3, 5, 7]和一个交换列表(3, 7), (5, 2)，我们可以先交换3和7得到[2, 7, 5, 3]，再交换5和2得到[5, 7, 2, 3]，最终得到可能的排序最大的数组。
输入格式
- 第一行包含一个整数
n，(1 ≤ n ≤ 500)，表示数组中整数的个数。 - 第二行包含
n个整数a_i，(1 ≤ a_i ≤ 10^9)，表示整数数组。 - 第三行包含一个整数
m，(0 ≤ m ≤ 10^3)，表示交换列表的对数。 - 接下来的
m行，每行包含两个整数b_i,c_i，(1 ≤ b_i, c_i ≤ 10^9)，表示可以交换的整数对，题目保证每对整数都存在于数组中。
输出格式
输出一行，包含n个整数，表示最大排序数组。
样例输入
4
2 3 5 7
2
3 7
5 2样例输出
5 7 2 3测评数据规模
1 ≤ n ≤ 500，1 ≤ a_i, b_i, c_i ≤ 10^9，0 ≤ m ≤ 10^3。
思路：
并查集
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll W = 2e6 + 10;
ll n,m;
ll a[W],fa[W];
bool vis[W];
vector <ll> num[W];
ll find(ll i)
{if(fa[i] != i){fa[i] = find(fa[i]);}return fa[i];
}
void merge(ll u,ll v)
{ll u1 = find(u);ll v1 = find(v);if(u1 != v1){fa[v1] = u1; }
}
bool check(ll u,ll v)
{return find(u) == find(v);
}
int main(void)
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);map<ll,ll> mp;cin >> n ;for(ll i = 1 ; i <= n ; i++)fa[i] = i;for(ll i = 1 ; i <= n ; i++){cin >> a[i];mp[a[i]] = i;//数字对应数组的下标（出现的） }cin >> m;for(ll i = 1 ; i <= m ; i++){ll x,y;cin >> x >> y;if(!check(mp[x],mp[y]))merge(mp[x],mp[y]);}for(ll i = 1 ; i <= n ; i++){num[find(i)].push_back(a[i]); }for(ll i = 1 ; i <= n; i++){sort(num[i].begin(),num[i].end());}for(ll i = 1 ; i <= n ; i++){if(!num[find(i)].empty()){cout << num[find(i)].back() << " ";num[find(i)].pop_back(); }}return 0;
}
