leetcode: 并查集（一维问题，二维问题，并查集通用代码）

示例题目1，一维

• 题目

• 解法

class Solution {
private:
    vector<int> parent;  // 实现森林的父指针表示法   
    vector<int> nums;    // 记录每个名字的频数
    unordered_map<string, int> name2id;  // name, id
    vector<string> name;        // 纯姓名字符串
    void merge(int f, int s) {  // 归并
        int rootf = find(f);
        int roots = find(s);
        if (rootf == roots) return;
        if(name[rootf] < name[roots]) {   // 注意 字典序大的节点的根，连到字典序小的节点的根下面。
            parent[roots] = rootf;
            nums[rootf] += nums[roots];  // 注意汇总 当前集合的名字频数
        } else {
            parent[rootf] = roots;
            nums[roots] += nums[rootf];
        }
    }
    int find(int x) {                 // 返回节点的根节点
        while(x!=parent[x]) {
            parent[x] = parent[parent[x]];  // 压缩树
            x = parent[x];
        }
        return x;
    }
public:
    vector<string> trulyMostPopular(vector<string>& names, vector<string>& synonyms) {
        int n = names.size(), m = synonyms.size();
        if (n < 2 || m == 0) return names;
        for (int i = 0; i < n; ++i) {
            parent.push_back(i);
            string tmp = getname(names[i]);
            name.push_back(tmp);
            nums.push_back(getnum(names.at(i)));
            name2id[tmp] = i;
        }//此循环初始化 parent, name纯姓名，nums姓名频数，name2id,姓名对应节点id的map。
        for (int i = 0; i < m; ++i) {
            std::pair<string, string> namepair = get_names(synonyms.at(i));
            merge(name2id[namepair.first], name2id[namepair.second]);
        } // 此循环 根据 synonyms 合并 姓名节点所在的树。
        set<string> st; // 避免重复 
        for (int i = 0; i < n; ++i) {
            int t = find(i);
            st.insert(joint(name[t], nums.at(t)));
        } // 此循环将 每个根节点的姓名和对应频数记录，这就是结果。
        vector<string> ans(st.begin(), st.end());
        return ans;
    }
//  以下是对字符串操作的功能函数
    int getnum(string &name) {  // 获得频数
        string::size_type p1 = name.find_first_of('(');
        string::size_type p2 = name.find_first_of(')');
        string ans = name.substr(p1+1, p2-p1-1);
        /*for (string::size_type i = p1+1; i < p2; ++i) {
            ans.push_back(name[i]);
        }*/
        return atoi(ans.c_str());
    }
    string getname(string &name) {  // 获得纯姓名字符串
        string::size_type p = name.find_first_of('(');
        string ans=name.substr(0, p);
        /*for (string::size_type i = 0; i < p; ++i) {
            ans.push_back(name[i]);
        }*/
        return ans;
    }
    std::pair<string, string> get_names(string namepair) { //获得两个连通的纯姓名字符串
        string::size_type p = namepair.find_first_of(',');
        string s1 = namepair.substr(1, p-1), s2 = namepair.substr(p+1, namepair.size()-p-2);
        /*for (string::size_type i = 1; i < p; ++i) {
            s1.push_back(namepair[i]);
        }
        for (string::size_type i = p+1; i < namepair.size()-1; ++i) {
            s2.push_back(namepair[i]);
        }*/
        return std::make_pair(s1, s2);
    }

    string joint(string s, int n) {  // 将纯姓名字符串和频数合成一个字符串。
        string ans(s);
        ans += "(";
        ans += to_string(n);
        ans += ")";
        return ans;
    }
};

示例题目2，二维

class Solution {
private:
    int parent[20000]; 
    int size[20000];

    void merge(int a, int b) {
        int ra = find(a);
        int rb = find(b);
        if (ra==rb) return;
        if (size[ra] < size[rb]) {
            parent[ra] = rb;
            size[rb] += size[ra];
        } else {
            parent[rb] = ra;
            size[ra] += size[rb];
        }
    }
    int find(int x) {
        while (x != parent[x]) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }

public:    
    int removeStones(vector<vector<int>>& stones) {
        int N = stones.size();
        for (int i = 0; i <20000; ++i) {
            parent[i] = i;
            size[i] = 1;
        }
        for (auto &s : stones) {
            merge(s[0], s[1] + 10000);  
            // 注意： i表示行号，10000+i的i表示列号，行列号只要有一个相同，就会合并到同一个集合。
        }
        unordered_set<int> ust;
        for (auto &s : stones) {
            int r = find(s[0]);
            ust.insert(r);
        }
        return N - ust.size();
    }
};

并查集核心代码

class UnionFind {
private:
    int count; // 连通分量数量 
    vector<int> parent; // 实现森林的父指针表示法 
	vector<int> size; // 记录每个树的结点数量（这里称为重量）
public:
	UnionFind(int n) : count(n) {  // 构造函数
		for (int i = 0; i < n; ++i) {
			parent.push_back(i); // 初始状态，每个节点都是自己的父节点
			size.push_back(1);   // 初始状态，每个树的重量都是 1 .
		}
	}
    void merge(int a, int b) {  // 连通的节点合并到一棵树
        int ra = find(a);
        int rb = find(b);
        if (ra==rb) return;  // 已经在同一颗树了
        if (size[ra] < size[rb]) {  // 将 重量轻的树接到大树下，比较平衡
            parent[ra] = rb;
            size[rb] += size[ra];
        } else {
            parent[rb] = ra;
            size[ra] += size[rb];
        }
        count--; // 连通分量数量减少1
    }
    int find(int x) {  // 找到 x 节点的根节点
        while (x != parent[x]) {
            parent[x] = parent[parent[x]];  // 路径压缩，搭配小树接到大树下的操作，此find 的时间复杂度为 O(1)。
            x = parent[x];
        }
        return x;
    }
    bool connected(int p, int q) { // 判断节点 p 和 q 是否在同一个连通分量
		return find(p) == find(q);
	}
};