题目链接：http://codeforces.com/problemset/problem/691/D
给你n个数，各不相同，范围是1到n。然后是m行数a和b，表示下标为a的数和下标为b的数可以交换无数次。问你最后字典序最大的数列是什么。
将下面的a和b用并查集联系起来存到祖节点对应的数组中，然后从大到小排序数组，最后依次按照父节点的数组中的顺序输出。
也可以用dfs的方法解(略麻烦)，形成一个环路的就在一个数组中...
//并查集
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + ;
vector <int> ans[N];
vector <int> root;
int pos[N] , par[N] , a[N] , vis[N]; int Find(int n) {
if(n == par[n])
return n;
return par[n] = Find(par[n]);
} int main()
{
int n , m , u , v;
scanf("%d %d" , &n , &m);
for(int i = ; i <= n ; ++i) {
scanf("%d" , a + i);
par[i] = i;
}
while(m--) {
scanf("%d %d" , &u , &v);
u = Find(u) , v = Find(v);
if(u != v)
par[u] = v;
}
for(int i = ; i <= n ; ++i) {
int u = Find(i);
ans[u].push_back(a[i]);
if(!vis[u]) {
root.push_back(u);
vis[u] = true;
}
}
for(int i = ; i < root.size() ; ++i)
sort(ans[root[i]].rbegin() , ans[root[i]].rend());
for(int i = ; i < n ; ++i)
printf("%d " , ans[Find(i)][pos[Find(i)]++]);
printf("%d\n" , ans[Find(n)][pos[Find(n)]]);
return ;
}
//dfs
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + ;
struct Edge {
int next , to;
}edge[N << ];
vector <int> ans[N];
vector <int> Root;
int a[N] , head[N] , cnt , is[N] , pos[N] , believe[N];
bool vis[N]; inline void add(int u , int v) {
edge[cnt].next = head[u];
edge[cnt].to = v;
head[u] = cnt++;
} void dfs(int root , int u , int par) {
vis[u] = true;
is[u] = root;
ans[root].push_back(a[u]);
for(int i = head[u] ; ~i ; i = edge[i].next) {
int v = edge[i].to;
if(v == par || vis[v])
continue;
dfs(root , v , u);
}
} int main()
{
memset(head , - , sizeof(head));
int n , m , u , v;
scanf("%d %d" , &n , &m);
for(int i = ; i <= n ; ++i)
scanf("%d" , a + i);
while(m--) {
scanf("%d %d" , &u , &v);
add(u , v);
add(v , u);
}
for(int i = ; i <= n ; ++i) {
if(!vis[i]) {
Root.push_back(i);
believe[i] = Root.size() - ;
dfs(i , i , -);
}
}
for(int i = ; i < Root.size() ; ++i) {
sort(ans[Root[i]].rbegin() , ans[Root[i]].rend());
}
for(int i = ; i <= n ; ++i) {
printf("%d" , ans[ Root[believe[is[i]]] ][ pos[believe[is[i]]]++ ]);
if(i != n)
putchar(' ');
else
putchar('\n');
}
return ;
}