5.5 最大字典序

实验任务

给定一个$1\sim N$的全排列，给出$M$对可以交换的位置$(A_i,B_i)$。每一次，你可以选择一对位置，交换其位置上的数值。不限制操作次数，请问经过交换后，字典序最大的全排列是多少(字典序的定义请参考）。

数据输入

第一行输入包括两个整数，$N$和$M\ (1\leq N,M\leq 20000)$。第二行输入包括$N$个整数，表示$1\sim N$的全排列。接下去$M$行，每行包括两个整数$A_i,B_i\ (1\leq A_i,B_i\leq N,A_i\neq B_i)$，表示序列中$A_i$和$B_i$位置上的数可以交换。

数据输出

出入$N$个整数，表示最大字典序的序列。

输入示例	输出示例
5 3 1 5 4 2 3 1 3 3 5 2 4	4 5 3 2 1

源代码（dfs）

复制

#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;
#define maxn 20005

int data[maxn];
vector<int> change[maxn];
int set[maxn];
int index[maxn];
bool used[maxn];

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

void dfs(int i, int &len){
    used[i] = true;
    index[len] = i;
    set[len++] = data[i];
    for (int j = 0; j < change[i].size(); ++j){
        if (!used[change[i][j]]){
            dfs(change[i][j], len);
        }
    }
}

int main(){
    int n, m, i, j, u, v;
    scanf("%d%d", &n, &m);
    for (i = 1; i <= n; ++i){
        scanf("%d", data + i);
    }
    for (i = 0; i < m; ++i){
        scanf("%d%d", &u, &v);
        change[u].push_back(v);
        change[v].push_back(u);
    }
    memset(used, false, sizeof(used));
    for (i = 1; i <= n; ++i){
        if (!used[i]){
            int len = 0;
            dfs(i, len);
            sort(set, set + len, cmp);
            sort(index, index + len);
            for (j = 0; j < len; ++j){
                data[index[j]] = set[j];
            }
        }
    }
    printf("%d", data[1]);
    for (i = 2; i <= n; ++i){
        printf(" %d", data[i]);
    }
    printf("\n");
}

源代码（并查集）

复制

#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;
#define maxn 20005

int data[maxn];
vector<int> pos[maxn], vec[maxn];

class UFset {
public:
    int root[maxn];
    int rank[maxn];
    void init(int n) {
        for (int i = 0; i <= n; ++i) {
            root[i] = i;
            rank[i] = 0;
        }
    }
    int Find(int v) {
        return root[v] = root[v] == v ? v : Find(root[v]);
    }
    void Union(int x, int y){
        int rx = Find(x);
        int ry = Find(y);
        if (rx == ry)return;//已合并返回
        //未优化
        //root[rx] = ry;
        //return;
        //优化
        if (rank[rx] < rank[ry]){
            root[rx] = ry;//把x的祖先rx合并到y的祖先ry上。因以ry为根的树更高
        }
        else{
            root[ry] = rx;
            if (rank[rx] == rank[ry]){
                ++rank[rx];//若两树一样高，那么合并后，高度加一
            }
        }
    }
} ufset;

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

int main() {
    int n, m, i, j, u, v;
    scanf("%d%d", &n, &m);
    for (i = 1; i <= n; ++i) {
        scanf("%d", &data[i]);
    }
    ufset.init(n);
    for (i = 0; i < m; ++i) {
        scanf("%d%d", &u, &v);
        ufset.Union(u, v);
    }
    for (i = 1; i <= n; i++){
        int fa = ufset.Find(i);
        vec[fa].push_back(data[i]);
        pos[fa].push_back(i);
    }
    for (i = 1; i <= n; i++){
        sort(vec[i].begin(), vec[i].end(), cmp);
        for (j = 0; j<pos[i].size(); j++){
            data[pos[i][j]] = vec[i][j];
        }
    }
    printf("%d", data[1]);
    for (i = 2; i <= n; ++i) {
        printf(" %d", data[i]);
    }
    printf("\n");
}

设计思路与复杂度分析

位置A和B可以互换，位置B和C可以互换，则位置A和C也可以互换。先将可以互相交换的数都放入同一个集合，然后将同一个集合的数进行逆序排序，放入原来的集合对应的位置即可得到解。

查找集合的方法就不唯一了：

1. 将序列看做深林，每一个交换集看做一棵树，则使用$dfs$或者$bfs$遍历即可得到每一颗树；
2. 既然是集合问题，自然可以使用并查集实现。

以上算法都可以在$O(n\times logn)$时间复杂度内实现。