旋转跳跃

思路

当我们可以将 对 看作 条双向边之后，能交换位置的点可以看作是联通的，因此我们会得到若干个连通块，由于 对 的使用次数与顺序不受限制，因此在每一个连通块中可以通过若干次交换不同位置上的值，使得该连通块中的数值从小到大排序，即为该连通块所能得到的最小字典序，将每一个连通块都在块内排序之后，即为最终答案。
时间复杂度：

题解

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

class Solution {
#define maxn 100010
private:
    vector<int> g[maxn];
    vector<int> val, pos;
    bool vis[maxn];
    int p[maxn];
public:
    /**
     * 返回牛牛所能得到的字典序最小的排列
     * @param n int整型 
     * @param m int整型 
     * @param perm int整型vector 
     * @param Pair Point类vector 
     * @return int整型vector
     */
    void dfs(int x, int fa = 0) {
        if (vis[x]) return;
        vis[x] = 1;
        pos.push_back(x);
        for (auto v: g[x]) {
            if (v == fa) continue;
            dfs(v, x);
        }
    }

    vector<int> solve(int n, int m, vector<int>& perm, vector<Point>& Pair) {
        // write code here
        for (int i = 1; i <= n; ++i) {
            g[i].clear();
            vis[i] = false;
            p[i] = perm[i-1];
        }
        for (int i = 0; i < m; ++i) {
            g[Pair[i].x].push_back(Pair[i].y);
            g[Pair[i].y].push_back(Pair[i].x);
        }

        for (int i = 1; i <= n; ++i) {
            if (vis[i]) continue;
            pos.clear();
            val.clear();
            dfs(i);
            for (auto j: pos)
                val.push_back(p[j]);
            sort(val.begin(), val.end());
            sort(pos.begin(), pos.end());
            int sz = pos.size();
            for (int j = 0; j < sz; ++j)
                p[pos[j]] = val[j];
        }
        vector<int> ans;
        for (int i = 1; i <= n; ++i) ans.push_back(p[i]);
        return ans;
    }
};