1 //  2 //by coolxxx  3 //#include<bits/stdc++.h>  4 #include<iostream>  5 #include<algorithm>  6 #include<string>  7 #include<iomanip>  8 #include<map>  9 #include<stack> 10 #include<queue> 11 #include<set> 12 #include<bitset> 13 #include<memory.h> 14 #include<time.h> 15 #include<stdio.h> 16 #include<stdlib.h> 17 #include<string.h> 18 //#include<stdbool.h> 19 #include<math.h> 20 #define min(a,b) ((a)<(b)?(a):(b)) 21 #define max(a,b) ((a)>(b)?(a):(b)) 22 #define abs(a) ((a)>0?(a):(-(a))) 23 #define lowbit(a) (a&(-a)) 24 #define sqr(a) ((a)*(a)) 25 #define swap(a,b) ((a)^=(b),(b)^=(a),(a)^=(b)) 26 #define mem(a,b) memset(a,b,sizeof(a)) 27 #define eps (1e-8) 28 #define J 10 29 #define mod 1000000007 30 #define MAX 0x7f7f7f7f 31 #define PI 3.14159265358979323 32 #define N 1000004 33 using namespace std; 34 typedef long long LL; 35 int cas,cass; 36 int n,m,lll,ans; 37 int fa[N],next[N],last[N],c[N],a[N],b[N],d[N]; 38 bool mark[N]; 39 int zhao(int aa) 40 { 41     if(fa[aa]==0 || fa[aa]==aa)return aa; 42     return fa[aa]=zhao(fa[aa]); 43 } 44 bool cmp1(int aa,int bb) 45 { 46     return aa>bb; 47 } 48 bool cmp2(int aa,int bb) 49 { 50     return aa<bb; 51 } 52 int main() 53 { 54     #ifndef ONLINE_JUDGE 55 //    freopen("1.txt","r",stdin); 56 //    freopen("2.txt","w",stdout); 57     #endif 58     int i,j,k; 59     int x,y,fx,fy; 60 //    for(scanf("%d",&cass);cass;cass--) 61 //    for(scanf("%d",&cas),cass=1;cass<=cas;cass++) 62 //    while(~scanf("%s",s+1)) 63     while(~scanf("%d",&n)) 64     { 65         mem(last,0);mem(mark,0);mem(fa,0); 66         scanf("%d",&m); 67         for(i=1;i<=n;i++) 68             scanf("%d",c+i); 69         for(i=1;i<=m;i++) 70         { 71             scanf("%d%d",&x,&y); 72             fx=zhao(x); 73             fy=zhao(y); 74             fa[fy]=fx; 75         } 76         for(i=1;i<=n;i++) 77         { 78             fa[i]=zhao(i); 79             next[i]=last[fa[i]],last[fa[i]]=i; 80         } 81         for(i=1;i<=n;i++) 82         { 83             if(mark[c[i]])continue; 84             for(k=0,j=last[fa[i]];j;j=next[j]) 85             { 86                 a[++k]=c[j]; 87                 b[k]=j; 88             } 89             sort(a+1,a+1+k,cmp1); 90             sort(b+1,b+1+k,cmp2); 91             for(j=1;j<=k;j++) 92                 d[b[j]]=a[j],mark[a[j]]=1; 93         } 94         for(i=1;i<=n;i++) 95             printf("%d ",d[i]); 96         puts(""); 97     } 98     return 0; 99 }100 /*101 //102 103 //104 */

 1 #include<stdio.h> 2 #include<algorithm> 3 #define MAXN 1000002 4 using namespace std; 5  6 int a[MAXN],first[MAXN],to[2*MAXN],next[2*MAXN]; 7 int stack_a[MAXN],stack_loc[MAXN],ans[MAXN]; 8 bool vis[MAXN]; 9 int top;10 11 void dfs(int u)12 {13     int e,v;14 15     vis[u]=true;16     stack_a[top]=a[u];17     stack_loc[top++]=u;18     e=first[u];19     while(e)20     {21         v=to[e];22         if(!vis[v])dfs(v);23         e=next[e];24     }25 }26 27 int main()28 {29     int n,m,i,j,u,v;30 31     scanf("%d%d",&n,&m);32     for(i=1;i<=n;i++)scanf("%d",&a[i]);33     for(i=1;i<=m;i++)34     {35         scanf("%d%d",&u,&v);36         next[i]=first[u];37         next[i+m]=first[v];38         first[u]=i;39         first[v]=i+m;40         to[i]=v;41         to[i+m]=u;42     }43     for(i=1;i<=n;i++)44     {45         if(!vis[i])46         {47             top=0;48             dfs(i);49             sort(stack_a,stack_a+top);50             sort(stack_loc,stack_loc+top);51             for(j=0;j<top;j++)ans[stack_loc[j]]=stack_a[top-j-1];52         }53     }54     for(i=1;i<=n;i++)55     {56         printf("%d",ans[i]);57         printf("%c",i<n?‘ ‘:‘\n‘);58     }59 60     return 0;61 }