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;
}