algo-aha

并查集，查两点是否连通

参考：https://www.cs.princeton.edu/courses/archive/spring13/cos423/lectures/UnionFind.pdf

并查集只有两个操作，查（find）和并（unite）

int find(int x) {
    if (parent[x] != x) 
        parent[x] = find(parent[x]); // 路径压缩
    return parent[x];
}

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

合并时可以优化。用size[]记录集合大小，初始全为1，合并时以size较大集合作为父集合。

void unite(int x, int y) {
    int px = find(x), py = find(y);
    if (px == py) return;

    if (size[px] < size[py]) swap(px, py); 
    size[px] += size[py];
    parent[py] = px;
}

或者用rank[]记录集合的高，初始全为0，合并时以rank较大集合作为父集合。之所以叫rank[]不叫height[]，因为确切来说rank[]并不是高度，“路径压缩”后height[x]<=rank[x]。

void unite(int x, int y) {
    int px = find(x), py = find(y);
    if (px == py) return;

    if (rank[px] < rank[py]) swap(px, py);
    if (rank[px] == rank[py]) rank[px]++;
    parent[py] = px;
}

也有用str作key，用unordered_map<string, string>作parent的。

初始赋值可以写在find()中

string find(const string &s, unordered_map<string, string> &parent) {
    if (!parent.count(s)) parent[s] = s;
    
    if (parent[s] != s) 
        parent[s] = find(parent[s], parent);
    return parent[s];
}