题解 | #旋转跳跃#

思路：

题目的主要信息：

• 给出一个长为n的排列p，即1到n的任意一个组合
• 一共有m对，每对表示交换排列p中序号为和中的元素，注意是序号而不是下标
• m对使用次数与顺序不受限制，求任意次操作之后能得到的字典序最小的排列是什么

方法一：并查集
具体做法：
可以用并查集的思想来解决，解释一下为何是并查集：假设排列p中两个位置a与b可以交换，如果b与c还可以交换，那么事实上a与c也可以交换，即我们只要找到每个独立的可以交换的集合，单独对集合内的元素排序，然后从小到大只排列集合中这些位置，就可以得到集合中我们要求的字典序最小。处理完每一个集合就是我们的全部字典序最小。

而要将所有单独的元素元素合并成各自的集合，就是并查集的内容。我们写一个并查集类，初始化为一个0到n-1的排列，对应每个节点的下标，并查集中有一个根节点，find函数找到每个节点的根节点，_union函数合并根节点一样的元素。然后我们用两个邻接表记录每个集合的下标和数值，遍历每个集合的邻接表，对其两部分排序，依次在其相应位置加入最小的元素就可以得到字典序最小。

#include <numeric> //iota函数的头文件
class DSU{ //建立并查集的类
public:
    DSU(int n) : p(n){ //初始化n个集合
        iota(begin(p), end(p), 0); //从0开始填充到n-1
    }
    int find(int x){ //找最大父节点
        if (p[x] == x)
            return x;
        return p[x] = find(p[x]); //递归查找是否存在
    }
    void _union(int u, int v) {
        int pu = find(u); //相互找到最大关联是否统一
        int pv = find(v);
        if (pu == pv) //已经合并了
            return;
        p[pu] = pv;
    }
    vector<int> p; 
};
class Solution {
public:
    vector<int> solve(int n, int m, vector<int>& perm, vector<Point>& Pair) {
        DSU dsu(n);
        vector<int> res(n);
        for(int i = 0; i < m; i++) //将所有的可以交换的元素合并
            dsu._union(Pair[i].x - 1, Pair[i].y - 1); //下标需要序号减1
        vector<vector<int> > Gid(n);
        vector<vector<int> > Gval(n);
        for(int i = 0; i < n; i++){
            Gid[dsu.find(i)].push_back(i); //某一块连通集合对应的下标有哪些
            Gval[dsu.find(i)].push_back(perm[i]); //某一块连通集合对应的数值有哪些
        }
        for(int i = 0; i < n; i++){
            sort(Gid[i].begin(), Gid[i].end());
            sort(Gval[i].begin(), Gval[i].end()); //对同一集合数值排序
            for(int j = 0; j < Gid[i].size(); j++) //依次加入小的到答案中，字典序就会更小
                res[Gid[i][j]] = Gval[i][j];
        }
        return res;
    }
};

复杂度分析：

• 时间复杂度：，最坏情况下并查集合并函数复杂度为，一共次，后续添加部分主体是排序，我们假设一共有个连通集合，其中每个集合的元素个数为，则排序总时间为，其中,其余复杂度低于这个值故舍去
• 空间复杂度：，并查集类的大小及其他辅助数组长度均为

方法二：dfs染色
具体做法：
对于并查集，我们也可以用染色的方式来完成，我们将可以交换的位置视作图的节点，构建图的连通表。然后遍历每个节点，对没有染色的节点进行dfs遍历整个连通的部分，染成相同的颜色，记录这个数字，并记录这部分的下标和数值，然后还是排序取最小使字典序最小。用数字表示颜色，数字为0表示未染色未访问过，每次dfs前数字加1代表换颜色。

class Solution {
public:
    int count = 0;
    void dfs(int v, int color, vector<int>& perm, vector<int>& label, vector<int>& id, vector<int>& val, vector<vector<int>>& G) {
        label[v] = color; //标记本块颜色
        id[count] = v; //记录id
        val[count] = perm[v]; //记录数值
        count++;
        for(int i = 0; i < G[v].size(); i++){ //相邻点染同色
            if (label[G[v][i]] == 0) //必须是没访问过的
                dfs(G[v][i], color, perm, label, id, val, G);
        }
    }
    vector<int> solve(int n, int m, vector<int>& perm, vector<Point>& Pair) {
        vector<vector<int> > G(n);
        vector<int> val(n, 0);
        vector<int> id(n, 0);
        vector<int> label(n, 0); //标记每个节点的颜色，颜色相同则连通
        for (int i = 0; i < m; i++) { //构建图
            G[Pair[i].x - 1].push_back(Pair[i].y - 1); //下标减1
            G[Pair[i].y - 1].push_back(Pair[i].x - 1);
        }
        int color = 0; //记录颜色的种类
        for (int i = 0; i < n; i++) { //遍历每个节点
            if (label[i] == 0){ //新的颜色，新的连通块
                color++;
                count = 0; //记录本次集合的元素个数
                dfs(i, color, perm, label, id, val, G); //dfs
                sort(val.begin(), val.begin() + count);
                sort(id.begin(), id.begin() + count);
                for (int j = 0; j < count; j++)  //排序后相同集合小的在前
                    perm[id[j]] = val[j];
            }
        }
        return perm;
    }
};

复杂度分析：

• 时间复杂度：，构建图一共循环次，后续添加部分主体是排序，我们假设一共有个连通集合，其中每个集合的元素个数为，则排序总时间为，其中,其余复杂度如dfs总共遍历次，低于这个值故舍去
• 空间复杂度：，辅助数组长度及递归栈深度最大为