把可以置换的关系建边，形成一张无向图，每一个连通块内的位置可以任意交换。
#pragma comment(linker, "/STACK:1024000000,1024000000") #include<cstdio> #include<cstring> #include<cmath> #include<cstdlib> #include<algorithm> #include<vector> #include<map> #include<set> #include<queue> #include<stack> #include<iostream> using namespace std; typedef long long LL; const double pi = acos(-1.0), eps = 1e-8; void File() { freopen("D:\in.txt", "r", stdin); freopen("D:\out.txt", "w", stdout); } inline int read() { char c = getchar(); while (!isdigit(c)) c = getchar(); int x = 0; while (isdigit(c)) { x = x * 10 + c - '0'; c = getchar(); } return x; } const int maxn=1000000+10; int n,m,p[maxn],ans[maxn],h[maxn],sz,q[maxn],cnt,tmp[maxn],num; struct Edge {int to,nx;} e[2*maxn]; bool f[maxn]; bool cmp(int a,int b) { return a>b; } void add(int u,int v) { e[sz].to=v; e[sz].nx=h[u]; h[u]=sz++; } void dfs(int x) { f[x]=1; q[cnt++]=x; for(int i=h[x];i!=-1;i=e[i].nx) if(!f[e[i].to]) dfs(e[i].to); } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) p[i]=read(); memset(h,-1,sizeof h); for(int i=1;i<=m;i++) { int x=read(),y=read(); add(x,y); add(y,x); } for(int i=1;i<=n;i++) { if(f[i]) continue; cnt=0; dfs(i); sort(q,q+cnt); for(int i=0;i<cnt;i++) tmp[i]=p[q[i]]; sort(tmp,tmp+cnt,cmp); for(int i=0;i<cnt;i++) ans[q[i]]=tmp[i]; } for(int i=1;i<=n;i++) printf("%d ",ans[i]); printf(" "); return 0; }