题目链接：
5 seconds
256 megabytes
standard input
standard output
You are given a permutation of the numbers 1, 2, ..., n and m pairs of positions (aj, bj).
At each step you can choose a pair from the given positions and swap the numbers in that positions. What is the lexicographically maximal permutation one can get?
Let p and q be two permutations of the numbers 1, 2, ..., n. p is lexicographically smaller than the q if a number 1 ≤ i ≤ n exists, sopk = qk for 1 ≤ k < i and pi < qi.
The first line contains two integers n and m (1 ≤ n, m ≤ 106) — the length of the permutation p and the number of pairs of positions.
The second line contains n distinct integers pi (1 ≤ pi ≤ n) — the elements of the permutation p.
Each of the last m lines contains two integers (aj, bj) (1 ≤ aj, bj ≤ n) — the pairs of positions to swap. Note that you are given apositions, not the values to swap.
Print the only line with n distinct integers p'i (1 ≤ p'i ≤ n) — the lexicographically maximal permutation one can get.
9 6
1 2 3 4 5 6 7 8 9
1 4
4 7
2 5
5 8
3 6
6 9
7 8 9 4 5 6 1 2 3 题意： 给一个数列,现在可以交换ai和bi,问能得到的最大的字典序的数列是什么; 思路： 把能交换位置的数放在同一个集合里;可以dfs找到,然后把这些数和位置排序对应就好了;不知道cf的数据怎么了; AC代码：
#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath> using namespace std; #define For(i,j,n) for(int i=j;i<=n;i++)
#define mst(ss,b) memset(ss,b,sizeof(ss)); typedef long long LL; template<class T> void read(T&num) {
char CH; bool F=false;
for(CH=getchar();CH<''||CH>'';F= CH=='-',CH=getchar());
for(num=;CH>=''&&CH<='';num=num*+CH-'',CH=getchar());
F && (num=-num);
}
int stk[], tp;
template<class T> inline void print(T p) {
if(!p) { puts(""); return; }
while(p) stk[++ tp] = p%, p/=;
while(tp) putchar(stk[tp--] + '');
putchar('\n');
} const LL mod=1e9+;
const double PI=acos(-1.0);
const LL inf=1e18;
const int N=1e6+;
const int maxn=;
const double eps=1e-; int n,m,p[N],a[N],b[N],ans[N],cnt,vis[N];
vector<int>ve[N];
void dfs(int x)
{
vis[x]=;
a[++cnt]=p[x];
b[cnt]=x;
int len =ve[x].size();
For(i,,len-)
{
int y =ve[x][i];
if(!vis[y]) dfs(y);
}
}
int cmp(int x,int y)
{
return x>y;
}
void solve()
{
sort(a+,a+cnt+,cmp);
sort(b+,b+cnt+);
For(i,,cnt)ans[b[i]]=a[i];
} int main()
{ read(n);read(m);
For(i,,n)read(p[i]);
int u,v;
For(i,,m)
{
read(u);read(v);
ve[u].push_back(v);
ve[v].push_back(u);
}
For(i,,n)
{
if(!vis[i])
{
cnt=;
dfs(i);
solve();
}
}
For(i,,n)printf("%d ",ans[i]); return ;
}