并查集

unionfind template

class UnionFind {
public:
    map<int, int> hash;

    UnionFind(int n)
    {
        for(int i = 0; i<n; i++)
        {
            hash[i] = -1;
        }
        hash[-1] = -1;
    }

    void change(int key, int val)
    {
        hash[key] = val;
    }

    int find(int key)
    {
        while(key != hash[key])
        {
            key = hash[key];
        }

        return key;
    }

    int compress_find(int key)
    {
        int org = key;
        while(key != hash[key])
        {
            key = hash[key];
        }

        while(org != key)
        {
            int next = hash[org];
            hash[org] = key;
            org = next;
        }

        return key;
    }

    bool bossunion(int a, int b)
    {
        int fa = find(a);
        int fb = find(b);

        if(fa == fb)
        {
            return false;
        }
        else
        {
            hash[fa] = fb;
            return true;
        }
    }
};