D. Swaps in Permutation

130 阅读 0 评论 86 点赞

我是靠谱客的博主正直蜜粉，这篇文章主要介绍D. Swaps in Permutation，现在分享给大家，希望可以做个参考。

这个题目的题意是，给一个长度为n的数字序列，其中各个元素均不相同且在1到n之间。然后给出一些位置的交换规则，即给出某些位置上的数是可以互相交换的。求出最终能交换得到的字典序最大的序列。

题目的解决方法并不难，举个例子：如果位置1能和位置2山的数交换，位置1又可以和位置3上的数交换，那么，位置1，2，3对应的数实际上是可以互相交换了，那么该字典序最大的序列就是位置1，2，3上的元素从到小的序列了。那么基于此，可以采用bfs,将从某个位置出发，能过交换的到的位置全部找出来，然后从大到小依次填到相应的位置上。最终得到的序列就是答案。具体请看代码。

复制代码

#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<set>
#include<algorithm>

using namespace std;

const int MAX = 1000010;

int a[MAX], c[MAX], vis[MAX];
vector<int>G[MAX];

int main(){
    int n,m;

while (scanf("%d%d",&n,&m) != EOF){
        for (int i = 1; i<=n; i++){
            scanf("%d", &a[i]);
            G[i].clear();
        }

int x, y;
        for (int i = 0; i<m; i++){
            scanf("%d%d",&x,&y);
            G[x].push_back(y);
            G[y].push_back(x);
        }

memset(vis, 0, sizeof(vis));
        int cnt = 0;

for (int i = 1; i<=n; i++){
            if (!vis[i]){

set<int>S, T;

cnt++;
                queue<int> q;
                q.push(i);
                vis[i] = cnt;

while (!q.empty()){
                    int u = q.front();
                    S.insert(u);
                    T.insert(a[u]);
                    q.pop();

for (int j = 0; j<G[u].size(); j++){
                        int v = G[u][j];

if (!vis[v]){
                            vis[v] = cnt;
                            q.push(v);
                        }
                    }
                }

set<int>::iterator it;
                set<int>::reverse_iterator rit;
                for (it = S.begin(),rit=T.rbegin(); it!=S.end(); it++,rit++){
                    c[*it] = *rit;
                }

}
        }
        printf("%d", c[1]);
        for (int i = 2; i<=n; i++) printf(" %d", c[i]);
        printf("n");
    }

return 0;
}

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
76
77
78
79
80
81
82
83
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<set>
#include<algorithm>

using namespace std;

const int MAX = 1000010;

int a[MAX], c[MAX], vis[MAX];
vector<int>G[MAX];

int main(){
    int n,m;

    while (scanf("%d%d",&n,&m) != EOF){
        for (int i = 1; i<=n; i++){
            scanf("%d", &a[i]);
            G[i].clear();
        }


        int x, y;
        for (int i = 0; i<m; i++){
            scanf("%d%d",&x,&y);
            G[x].push_back(y);
            G[y].push_back(x);
        }

        memset(vis, 0, sizeof(vis));
        int cnt = 0;

        for (int i = 1; i<=n; i++){
            if (!vis[i]){

                set<int>S, T;

                cnt++;
                queue<int> q;
                q.push(i);
                vis[i] = cnt;

                while (!q.empty()){
                    int u = q.front();
                    S.insert(u);
                    T.insert(a[u]);
                    q.pop();

                    for (int j = 0; j<G[u].size(); j++){
                        int v = G[u][j];

                        if (!vis[v]){
                            vis[v] = cnt;
                            q.push(v);
                        }
                    }
                }

                set<int>::iterator it;
                set<int>::reverse_iterator rit;
                for (it = S.begin(),rit=T.rbegin(); it!=S.end(); it++,rit++){
                    c[*it] = *rit;
                }


            }
        }
        printf("%d", c[1]);
        for (int i = 2; i<=n; i++) printf(" %d", c[i]);
        printf("n");
    }

    return 0;
}