Educational Codeforces Round 14 D. Swaps in Permutation（并查集）

题目链接：http://codeforces.com/contest/691/problem/D

题意：

题目给出一段序列，和m条关系，你可以无限次互相交换这m条关系 ，问这条序列字典序最大可以为多少

思路：

并查集维护这m条关系，用个vector存一下当前点所能到达的点，拍下序大的优先，输出的时候输出当前点所能找到的最大的数，已输出的标记下就好了。

实现代码：

#include<bits/stdc++.h>
using namespace std;
const int M = 1e6+10;
int f[M],vis[M],a[M];

int Find(int x){
    if(x==f[x])return x;
    return f[x]=Find(f[x]);
}

void mix(int x,int y){
    int fx = Find(x);
    int fy = Find(y);
    if(fx != fy) f[fx] = fy;
}

bool cmp(int a,int b){
    return a > b;
}

vector<int>v[M];

int main()
{
    int n,x,y,m;
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;i ++){
        scanf("%d",&a[i]);
        f[i] = i;
    }
    for(int i = 1;i <= m;i ++){
        scanf("%d%d",&x,&y);
        mix(x,y);
    }
    for(int i = 1;i <= n;i ++)
        v[Find(i)].push_back(a[i]);
    for(int i = 1;i <= n;i ++)
        sort(v[i].begin(),v[i].end(),cmp);
    for(int i = 1;i <= n;i ++){
        printf("%d ",v[Find(i)][vis[Find(i)]++]);
    }
}