【牛客编程巅峰赛S1第3场】旋转跳跃 —— 并查集

题目

有一个长为 的排列 ，与 对 。
每对 表示可以将 的值与 的值互换。 对 的使用顺序与次数不限。
求任意次操作之后能得到的字典序最小的排列是什么？

输入
第三个参数为初始排列 。
第四个参数为 对 。

返回
字典序最小的排列。

解题思路

可以将每一个下标看作图中的一个节点，把互换的关系看作是连接两个节点的边，那么由于互换操作具有传递性，即如果下标 a 和 b 的值互换，下标 b 和 c 的值互换，则下标 a 和 c 的值也可以互换。也就是说，所有互换的下标属于同一个连通分量。因此，可以使用并查集来维护这种连通分量的关系。

首先遍历 对 ，构造并查集。可以互换值的两个下标属于同一个连通分量，因此将两个下标进行合并。

然后遍历所有的下标。将属于同一个连通分量的下标作为一个集合，分别对集合中的下标和值排序，并将其中较小的下标对应较小的值。

C++代码

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

class UnionFind {
    vector<int> parent;

public:
    UnionFind(int n){
        parent.resize(n, 0);
        iota(parent.begin(), parent.end(), 0);
    }

    int find(int i){
        if(i == parent[i]){
            return i;
        }
        parent[i] = find(parent[i]);
        return parent[i];
    }

    void unite(int x, int y){
        parent[find(x)] = find(y);
    }
};

class Solution {
public:
    /**
     * 返回牛牛所能得到的字典序最小的排列
     * @param n int整型 
     * @param m int整型 
     * @param perm int整型vector 
     * @param Pair Point类vector 
     * @return int整型vector
     */
    vector<int> solve(int n, int m, vector<int>& perm, vector<Point>& Pair) {
        // write code here
        UnionFind uf(n);
        for(int i=0; i<m; ++i){
            uf.unite(Pair[i].x - 1, Pair[i].y - 1);
        }
        vector<vector<int>> vi(n);
        vector<vector<int>> va(n);
        for(int i=0; i<n; ++i){
            vi[uf.find(i)].push_back(i);
            va[uf.find(i)].push_back(perm[i]);
        }
        for(int i=0; i<n; ++i){
            sort(vi[i].begin(), vi[i].end());
            sort(va[i].begin(), va[i].end());
            for(int j=0; j<vi[i].size(); ++j){
                perm[vi[i][j]] = va[i][j];
            }
        }
        return perm;
    }
};