leetcode765

1.记录索引交换

class Solution {
public:
    int minSwapsCouples(vector<int>& row) {
        int len=row.size();
        vector<int> idx(len,-1);
        int ret=0;
        for(int i=0;i<len;++i){
            int tmp=conv(row[i]);
            //cout<<"i:"<<i<<endl;
            if(idx[tmp]!=-1){    
                //cout<<2<<endl;
                int tmp_idx=conv(idx[tmp]);
                if(tmp_idx!=i){
                    //cout<<3<<endl;
                    ++ret;
                    swap(tmp_idx,i,row);
                    idx[row[i]]=i;
                    //for(int i:row)cout<<"row:"<<i<<endl;
                }
            }else{
                //cout<<1<<endl;
                idx[row[i]]=i;
            }
        }
        return ret;
    }
    int conv(int num){
        return num%2==0?num+1:num-1;
    }
    void swap(int a,int b,vector<int>& row){
        row[a]=row[a]^row[b];
        row[b]=row[a]^row[b];
        row[a]=row[a]^row[b];
    }
};

2.计算图中环的个数和成对的边个数。最大值2n，总量为n，每个不用交换的边-1，每个环-1，判断是否成环这里使用union find，只要新的边的两点属于同一集合则为环。

//并查集
class UF{
    // 节点 x 的根节点是 parent[x]
    private: 
    std::vector<int> parent;
    // 新增一个数组记录树的“重量”
    std::vector<int> rank;
    /* 构造函数，n 为图的节点总数 */
    public: 
    UF(int n) : parent(std::vector<int>(n)),rank(std::vector<int>(n, 0))
    {
        // 一开始互不连通
        for (int i = 0; i < n; i++){
            // 父节点指针初始指向自己
            //parent[i] = i;
            // 重量应该初始化 1
            //rank[i] = 1;
            // 父节点指针初始指向自己
            parent[i] = i%2==0?i+1:i;
            // 重量应该初始化 1
            rank[i] = i%2==0?1:2;
        }
    }

    /* 将 p 和 q 连接 */    
    void connect(int p, int q){
        int rp=find(p);
        int rq=find(q);
        if(rp==rq){
            return;
        }
        if(rank[rp]>rank[rq]){
            parent[rq]=rp;
            rank[rp] += rank[rq];
        }else{
            parent[rp]=rq;
            rank[rq] += rank[rp];
        }
    };
    /* 判断 p 和 q 是否连通 */
    bool connected(int p, int q){
        int rp=find(p);
        int rq=find(q);
        return parent[rp]==parent[rq];
    };

    /* 返回某个节点 x 的根节点 */
    private: 
    int find(int x) {
        // 根节点的 parent[x] == x
        while(x!=parent[x]){
            // 进行路径压缩
            parent[x] = parent[parent[x]];
            x=parent[x];
        }
        return x;
    }
};
class Solution {
public:
    int minSwapsCouples(vector<int>& row) {
        int len=row.size();
        UF uf(len);
        int ret=len/2;
        for(int i=0;i<len;i+=2){
            //uf初始化时已经将成对节点connect
            if(uf.connected(row[i],row[i+1])){
                --ret;
            }else{
                uf.connect(row[i],row[i+1]);
            }
        }
        return ret;
    }
};