codeforces 691D D. Swaps in Permutation(dfs)

题目链接：

D. Swaps in Permutation

time limit per test

5 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

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, ..., n. p is lexicographically smaller than the q if a number 1 ≤ i ≤ n exists, sopk = 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 ≤ pi ≤ n) — the elements of the permutation p.

Each of the last m lines contains two integers (aj, bj) (1 ≤ aj, bj ≤ n) — 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 p'i (1 ≤ p'i ≤ n) — 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

题意：

给一个数列,现在可以交换ai和bi,问能得到的最大的字典序的数列是什么;

思路：

把能交换位置的数放在同一个集合里;可以dfs找到,然后把这些数和位置排序对应就好了;不知道cf的数据怎么了;

AC代码：

#include <bits/stdc++.h>

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

using namespace std;

#define For(i,j,n) for(int i=j;i<=n;i++)

#define mst(ss,b) memset(ss,b,sizeof(ss));

typedef  long long LL;

template<class T> void read(T&num) {

    char CH; bool F=false;

    for(CH=getchar();CH<''||CH>'';F= CH=='-',CH=getchar());

    for(num=;CH>=''&&CH<='';num=num*+CH-'',CH=getchar());

    F && (num=-num);

}

int stk[], tp;

template<class T> inline void print(T p) {

    if(!p) { puts(""); return; }

    while(p) stk[++ tp] = p%, p/=;

    while(tp) putchar(stk[tp--] + '');

    putchar('\n');

}

const LL mod=1e9+;

const double PI=acos(-1.0);

const LL inf=1e18;

const int N=1e6+;

const int maxn=;

const double eps=1e-;

int n,m,p[N],a[N],b[N],ans[N],cnt,vis[N];

vector<int>ve[N];

void dfs(int x)

{

    vis[x]=;

    a[++cnt]=p[x];

    b[cnt]=x;

    int len =ve[x].size();

    For(i,,len-)

    {

        int y =ve[x][i];

        if(!vis[y]) dfs(y);

    }

}

int cmp(int x,int y)

{

    return x>y;

}

void solve()

{

    sort(a+,a+cnt+,cmp);

    sort(b+,b+cnt+);

    For(i,,cnt)ans[b[i]]=a[i];

}

int main()

{

    read(n);read(m);

    For(i,,n)read(p[i]);

    int u,v;

    For(i,,m)

    {

        read(u);read(v);

        ve[u].push_back(v);

        ve[v].push_back(u);

    }

    For(i,,n)

    {

        if(!vis[i])

        {

            cnt=;

            dfs(i);

            solve();

        }

    }

    For(i,,n)printf("%d ",ans[i]);

        return ;

}

巴特西

codeforces 691D D. Swaps in Permutation(dfs)

最新文章

热门文章