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）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#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");
}

源代码（并查集）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#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)\)时间复杂度内实现。

0%