浙江财经大学
信工学院ACM集训队

CodeForces Round#691.D Swaps in Permutation

本文由 Ocrosoft 于 2016-08-10 15:46:34 发表

You are given a permutation of the numbers 1, 2, …, n and m pairs of positions (aj, bj).

At each step you can choose a pair from the given positions and swap the numbers in that positions. What is the lexicographically maximal permutation one can get?

Let p and q be two permutations of the numbers 1, 2, …, np is lexicographically smaller than the q if a number 1 ≤ in exists, so pk = qk for 1 ≤ k < i and pi < qi.

Input

The first line contains two integers n and m (1 ≤ n, m ≤ 106) — the length of the permutation p and the number of pairs of positions.

The second line contains n distinct integers pi (1 ≤ pin) — the elements of the permutation p.

Each of the last m lines contains two integers (aj, bj) (1 ≤ aj, bjn) — the pairs of positions to swap. Note that you are given apositions, not the values to swap.

Output

Print the only line with n distinct integers pi (1 ≤ pin) — the lexicographically maximal permutation one can get.

Example
input
9 6
1 2 3 4 5 6 7 8 9
1 4
4 7
2 5
5 8
3 6
6 9

output
7 8 9 4 5 6 1 2 3

Solution:

题意:给出一个序列,并且给出一些成对的下标,表示这些下标可以无限次交换。要求输出交换后字典序最大的一组。

思路:a能跟b换,b能跟c换,c能跟d换,那么这些之间都可以随意换,所以可以用并查集并起来,也就是说可以把这些坐标分成若干块,然后这些块内部降序排序,最后放回到原位置,输出即可。脑洞,呵呵..

#include <set>
#include <map>
#include <list>
#include <cmath>
#include <stack>
#include <queue>
#include <ctime>
#include <string>
#include <cstdio>
#include <vector>
#include <cctype>
#include <climits>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define ms(a) memset(a,0,sizeof(a))
#define INF INT_MAX
#define MAXN 1000000+10
using namespace std;
int n,m;
int num[MAXN];
int pre[MAXN];
vector<int> a[MAXN],b[MAXN];
int ans[MAXN];
int find(int x)
{
    if(pre[x]!=x)pre[x]=find(pre[x]);
    return pre[x];
}
void Union(int x,int y)
{
    int fx=find(x),fy=find(y);
    pre[fx]=fy;
}
int main()
{
    cin>>n>>m;
    for(int i=1; i<=n; i++)
    {
        pre[i]=i;
        scanf("%d",&num[i]);
    }
    for(int i=0; i<m; i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        Union(a,b);
    }
    for(int i=1; i<=n; i++)
    {
        int x=find(i);
        a[x].push_back(i);
        b[x].push_back(-num[i]);
    }
    for(int i=1; i<=n; i++)
    {
        sort(b[i].begin(),b[i].end());
        for(int j=0; j<a[i].size(); j++)
            ans[a[i][j]]=-b[i][j];
    }
    for(int i=1; i<=n; i++)
        printf("%d ",ans[i]);
    return 0;
}

欢迎转载,请保留出处与链接。Ocrosoft » CodeForces Round#691.D Swaps in Permutation

点赞 (0)or拍砖 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址