codeforces 691D Swaps in Permutation DFS

这个题刚开始我以为是每个交换只能用一次，然后一共m次操作

结果这个题的意思是操作数目不限，每个交换也可以无限次

所以可以交换的两个位置连边，只要两个位置连通，就可以呼唤

然后连通块内排序就好了

#include <vector>

#include <iostream>

#include <queue>

#include <cmath>

#include <map>

#include <cstring>

#include <algorithm>

#include <cstdio>

using namespace std;

typedef long long LL;

const int N=1e6+;

const LL mod=1e9+;

struct Edge{

  int v,next;

}edge[N<<];

int head[N],tot,a[N],n,m,cnt;

vector<int>bcc[N],ran[N];

void add(int u,int v){

  edge[tot].v=v;

  edge[tot].next=head[u];

  head[u]=tot++;

}

bool vis[N];

void dfs(int u){

  vis[u]=true;

  bcc[cnt].push_back(a[u]);

  ran[cnt].push_back(u);

  for(int i=head[u];~i;i=edge[i].next)

    if(!vis[edge[i].v])dfs(edge[i].v);

}

int main(){

   scanf("%d%d",&n,&m);

   for(int i=;i<=n;++i)

    scanf("%d",&a[i]);

   memset(head,-,sizeof(head));

   for(int i=;i<=m;++i){

     int u,v;scanf("%d%d",&u,&v);

     add(u,v);add(v,u);

   }

  for(int i=;i<=n;++i){

   if(vis[i])continue;

    ++cnt;dfs(i);

  }

  for(int i=;i<=cnt;++i){

    sort(bcc[i].begin(),bcc[i].end());

    sort(ran[i].begin(),ran[i].end());

    int sz=bcc[i].size()-;

    for(int j=,k=sz;j<=sz;++j,--k)

      a[ran[i][j]]=bcc[i][k];

  }

  for(int i=;i<n;++i)printf("%d ",a[i]);

    printf("%d\n",a[n]);

  return ;

}