首页 > 代码库 > Codeforces 691D. Swaps in Permutation
Codeforces 691D. Swaps in Permutation
题目链接:http://codeforces.com/problemset/problem/691/D
题意:
给你一个含有 N 个不重复数的序列, 以及 M 对形如 (ai, bj) 的数, (ai ,bj) 代表着可以把第 ai 个数可以和第 bj 个数进行交换, 问如何交换才能使得变换后的字典序最大,每个变化可选可不选,也可选多次.
思路：
可以想到, 如果 a 可以和 b 换, b 可以和 c 换, 那么 a 就可以间接的和 c 换, 依次类推, 如果某些位置直接可以变换, 那么与这些位置有关系的位置,也可以互相交换. 那么可以把这 N 个点所处的 N 个位置看成一张图上的点, 如果两个位置上的数可以交换, 那么说明图中代表这两个位置的点之间存在一条边,那么这些点和边将会形成若干个连通分支,一个连通分支里的所有点都可以互相交换. 假设某一个连通分支包含着 k 个位置, 既可以说明这 k 个位置上的数可以任意互相交换(直接或者间接),那么由于这 k 个位置上同时又有 k 个数, 这时只需要把这 k 个数按照从大到小的顺序分别填到 k 个位置上, 且这 k 个位置是从前到后的,即从小到大的.所以利用DFS遍历每个连通分支, 记录位置的同时记录位置上的数, 然后把所有这些数从大到小的填到 从小到大的位置上, 这样满足一个位置恰好一个数, 遍历所有连通分支一次, 每个位置上最终的数就确定了.
代码:
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 typedef long long LL; 5 6 const int MAXN = 1000000; 7 int pt[MAXN + 3]; //存储每个数 8 int visit[MAXN + 3]; //DFS时的标记数组 9 int n, m;10 int ind[MAXN + 3]; //位置11 int value[MAXN + 3];//值12 int len;//长度13 14 int head[MAXN + 3];//链式前向星存图15 struct NODE {int to; int next; };16 NODE edge[MAXN * 2 + 3];17 18 void DFS(int u) { //从位置 u 开始搜索19 for(int k = head[u]; k != -1; k = edge[k].next){//访问每个与位置 u 相邻的位置20 if(!visit[edge[k].to]){ //未访问过这个位置21 visit[edge[k].to] = 1;22 ind[len] = edge[k].to, value[len++] = pt[edge[k].to - 1];//记录与当前位置相通的位置 以及 每个位置上的数23 DFS(edge[k].to);24 }25 }26 }27 28 int cmp(int a, int b) { return a > b; }29 30 int main() {31 ios_base::sync_with_stdio(0); cin.tie(0);32 //freopen("output", "w", stdout);33 cin >> n >> m;34 memset(pt, 0, sizeof(pt));35 for(int i = 0; i < n; i++) cin >> pt[i];36 memset(head, -1, sizeof(head));37 for(int i = 1; i <= m; i++) { //以位置为点建图,如果两个位置上的数可以交换那么就说明这两个位置之间存在一条边.38 int u, v;39 cin >> u >> v;40 edge[2 * i - 1].to = v; //链式前向星存图,每条边存两次41 edge[2 * i - 1].next = head[u];42 head[u] = 2 * i - 1;43 edge[2 * i].to = u;44 edge[2 * i].next = head[v];45 head[v] = 2 * i;46 }47 memset(visit, 0, sizeof(visit));48 int ans[MAXN + 3] = {0};//保存答案49 for(int i = 1; i <= n; i++) {//从第一个位置开始搜索与其相通的其他位置50 if(!visit[i]) {51 visit[i] = 1;52 len = 0;//与当前位置相通的位置的个数53 ind[len] = i;54 value[len++] = pt[i - 1];55 DFS(i);56 sort(ind, ind + len);//对访问到的位置从小到达排序57 sort(value, value + len, cmp);//对访问到的值从大到下排序58 for(int j = 0; j < len; j++) ans[ ind[j] ] = value[j];//把较大的值填入到位置较小的位置，每个数恰好只填一次，每个位置也仅有一个数可填59 }60 }61 for(int i = 1; i <= n; i++) cout << (i == 1 ? "":" ") << ans[i];62 cout << endl;63 return 0;64 }
Codeforces 691D. Swaps in Permutation
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。