并差集.md

并查集

适用于解决两个问题：

• 将两个集合合并
• 询问两个元素是否在一个集合中

存储方式p[x]代表这个值的父节点编号，当一个集合的根节点为p[x]=x时，代表这个节点是根结点。

const int N = 100010;
int p[N], size[N];//维护每个集合的大小，只记录给根结点
int find(int x) {
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

void merge(int x, int y ){
    int xf = find(x);
    int yf = find(y);
    if(xf != yf) {
        size[yf] += size[xf];
        return p[xf] = yf;
    }
}

LeetCode 721. 账户合并. 给定一个列表 accounts，每个元素 accounts[i] 是一个字符串列表，其中第一个元素 accounts[i][0] 是 名称 (name)，其余元素是 emails 表示该帐户的邮箱地址。现在，我们想合并这些帐户。如果两个帐户都有一些共同的邮件地址，则两个帐户必定属于同一个人。请注意，即使两个帐户具有相同的名称，它们也可能属于不同的人，因为人们可能具有相同的名称。一个人最初可以拥有任意数量的帐户，但其所有帐户都具有相同的名称。合并帐户后，按以下格式返回帐户：每个帐户的第一个元素是名称，其余元素是按顺序排列的邮箱地址。accounts 本身可以以任意顺序返回。

class Solution {
public:
    //用一个f来表示不同姓名的根结点
    vector<int> f;
    unordered_set<string> isApperaed;
    unordered_map<string, int> father;
    //保留字符串的父节点
    int find(int x) {
        if(f[x] != x) f[x] = find(f[x]);
        return f[x];
    }
    void merge(int x, int y){
        int xf = find(x);
        int yf = find(y);
        if(xf != yf) f[yf] = xf;
    }
    vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
        vector<vector<string>> ans;
        f = vector<int>(accounts.size(),0);
        for(int i = 0; i < accounts.size(); i++) f[i] = i;//初始化每个人就是自己

        for(int i = 0; i < accounts.size(); i++){
            for(int j = 1; j < accounts[i].size(); j++){
                if(!isApperaed.count(accounts[i][j]) ){//第一次出现
                    isApperaed.insert(accounts[i][j]);
                    father[accounts[i][j]] = i;
                } else {
                    merge(father[accounts[i][j]], i);
                }
            }
        }
        unordered_map<int, set<string>> actMails;
        //去重
        for(int i = 0; i < accounts.size(); i++){
            int t = find(i);//根结点
            int len = accounts[i].size();
            for(int j = 1; j<len; j++) actMails[t].insert(accounts[i][j]);
        }
        for(auto acc: actMails){
            vector<string> tmp;
            tmp.push_back(  accounts[acc.first][0] );
            for(auto email: acc.second){ tmp.push_back(email);}
            ans.push_back(tmp);
        }
        return ans;
    }
};

图中找环

LeetCode 685. 冗余连接 II

对于一条新加入的边[u,v]，判断是否存在冲突，冲突的意思是v是否已经有了父节点。如果有了则为冲突的边，如果没有继续判断。u,v的父亲节点是否相同，以及u是否是v的父亲节点，如果是，则存在环，记录导致环的边，如果不是则在并查集中合并。

class Solution {
public:
    struct UnionFind {
        vector<int> parent;
        UnionFind(int n) {
            parent.resize(n);
            for(int i = 0; i < n; i++) {
                parent[i] = i;
            }
        }
        int find(int index){
            return index == parent[index] ? index : parent[index] = find(parent[index]);
        } 
        void merge(int x, int y) {
            int xf = find(x);
            int yf = find(y);
            if (xf != yf) {
                parent[xf] = yf;
            }
        }
    };

    vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {
        int n = edges.size();
        UnionFind uf(n+1);
        auto parent = vector<int>(n+1);
        for(int i = 1; i <= n; i++){
            parent[i] = i;
        }

        int conflict = -1;
        int cycle = -1;
        for(int i = 0; i < n; i++){
            auto edge = edges[i];
            int node1 = edge[0], node2 = edge[1];
            if (parent[node2] != node2) {
                conflict = i;
            } else {
                parent[node2] = node1;
                if (uf.find(node1) == uf.find(node2)){
                    cycle = i;
                } else {
                    uf.merge(node1, node2);
                }
            }
        }
        if (conflict < 0) {
            auto redundant = vector<int> {edges[cycle][0], edges[cycle][1]};
            return redundant;
        } else {
            auto conflictEdge = edges[conflict];
            if (cycle >= 0) {
                auto redundant = vector<int> {parent[conflictEdge[1]], conflictEdge[1]};
                return redundant;
            } else {
                auto redundant = vector<int> {conflictEdge[0], conflictEdge[1]};
                return redundant;
            }
        }
    }
};