题意：

给你一个 $1\sim n$ 的排列 $p$ 和 $m$ 个数对 $(x_i,y_i)$ ，每对数对表示可以将 $p_{x_i}$ 和 $p_{y_i}$ 两个元素交换，你可以交换任意多次，问任意操作次后能得到的字典序最小的排列是什么？

解法一（BFS，不可AC）

用BFS枚举所有可能的排列，最后取字典序最小的排列

判重可以将排列转换成字符串再用unordered_map进行判重

具体的：

1. 刚开始往队列中push初始排列 $p$ ，并且标记访问过

2. 当队列非空时一直循环

3. 取出队头的排列，若当前排列比答案更优，则替换答案，枚举所有一次交换后会变成的排列，判重后再push到队列中，并且标记该排列访问过

4. 重复步骤2

代码：

class Solution {
public:
    string p_to_string(vector<int>& p){
        //将排列转换成字符串，便于使用unordered_map
        string ret(p.size(),' ');
        for(int i=0;i<p.size();i++){
            ret[i]=p[i];
        }
        return ret;
    }
    vector<int> string_to_p(string& s){
        //将字符串转换为排列
        vector<int> ret(s.size());
        for(int i=0;i<s.size();i++){
            ret[i]=s[i];
        }
        return ret;
    }
    vector<int> solve(int n, int m, vector<int>& perm, vector<Point>& Pair) {
        unordered_map<string,bool> vis;//用于判重
        queue<string> que;//bfs所用队列
        string st=p_to_string(perm);
        que.push(st);//将初始排列push入队列
        vis[st]=true;
        string ans=st;
        while(!que.empty()){
            string t=que.front();//取出队头
            que.pop();
            if(t<ans){
                ans=t;//更新答案
            }
            for(auto p:Pair){//枚举所有一次交换后的情况
                string ex=t;
                swap(ex[p.x-1],ex[p.y-1]);
                if(!vis[ex]){
                    que.push(ex);
                    vis[ex]=true;
                }
            }
        }
        return string_to_p(ans);//返回答案
    }
};

时间复杂度： $O(n!)$ ，最坏情况有 $n!$ 排列方案，故时间复杂度为 $O(n!)$

空间复杂度： $O(n!)$ ，最坏情况有 $n!$ 排列方案，需要存储 $n!$ 个排列，故空间复杂度为 $O(n!)$

解法二（并查集）

我们考虑将 $m$ 个数对看成 $m$ 条无向边，然后连成若干个联通图

以本题样例来说：

其中 $\{1,2,3,4\}$ 是联通的，我们发现由于可以交换任意多次，故在同一个联通图内元素的顺序我们可以任意指定

我们先将同一个连通块内的下标标红

然后再将同一个连通块内的元素排序

这样我们就得到本题样例最优的答案了

那么我们只需要对若干个联通图内的元素进行从小到大排序，最后拼接起来的一定是字典序最小的排列

具体的判断连通性我们可以使用并查集快速解决

代码：

/**
 * struct Point {
 *	int x;
 *	int y;
 * };
 */

class Solution {
public:
    int fa[100001];//并查集父节点数组
    int find_root(int x){//并查集寻找根节点
        if(fa[x]==x)return x;
        return fa[x]=find_root(fa[x]);//路径压缩
    }
    struct node{
        int idx,val;//idx为对应在排列中的下标，val为对应元素值
        inline node(int idx,int val):idx(idx),val(val){}
        inline bool operator < (const node& other)const{
            return val<other.val;//按照元素大小排序
        }
    };
    vector<node> datas[100001];//存储不同连通块内的元素
    vector<int> solve(int n, int m, vector<int>& perm, vector<Point>& Pair) {
        for(int i=1;i<=n;i++){
            fa[i]=i;//并查集初始化
        }
        for(int i=1;i<=n;i++){
            datas[i].clear();//多测清空
        }
        for(auto p:Pair){
            //构造联通图
            int x=p.x,y=p.y;
            if(find_root(x)==find_root(y))continue;
            //合并
            fa[find_root(x)]=find_root(y);
        }
        for(int i=1;i<=n;i++){
            //将元素放到对应的连通块内
            datas[find_root(i)].push_back(node(i-1,perm[i-1]));
        }
        for(int i=1;i<=n;i++){
            //不同连通块内进行排序
            sort(datas[i].begin(),datas[i].end());
        }
        for(int i=1;i<=n;i++){
            vector<int> idxs;//存储不同连通块内的元素在排列中原本的下标
            for(auto x:datas[i]){
                idxs.push_back(x.idx);
            }
            sort(idxs.begin(),idxs.end());//下标从小到大排序
            for(int j=0;j<idxs.size();j++){
                perm[idxs[j]]=datas[i][j].val;//将已经排好序的元素依次放入排列中
            }
        }
        return perm;//返回答案
    }
};

时间复杂度： $O(nlogn)$ ，对元素排序的复杂度是 $O(nlogn)$ 的，路径压缩并查集复杂度是近似 $O(1)$ 的，故总的时间复杂度为 $O(nlogn)$

空间复杂度： $O(n)$ ，并查集父节点数组、连通块数组都是 $O(n)$ 大小的，故总的空间复杂度为 $O(n)$

题解 | #旋转跳跃#

题意：

解法一（BFS，不可AC）

解法二（并查集）