Connecting Graph 2

int Query(int keyA)

return the number of the nodes that are in the same set of key A.

Hint: just record keyA's boss's number of connections and return that number

Solution

class unionFind
{
public:

    map<int, int> hash;
    map<int, int> connections;

    unionFind()
    {
    }

    void init(int n)
    {
        for(int i = 1; i <= n; i++)
        {
            hash[i] = i;
            connections[i] = 1;
        }
    }

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

    int compressfind(int key)
    {
        int boss = find(key);

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

        return boss;
    }

    bool bossunion(int key1, int key2)
    {
        int boss1 = compressfind(key1);
        int boss2 = compressfind(key2);
        if(boss1 == boss2)
        {
            return false;
        }
        else
        {
            hash[boss1] = boss2;
            connections[boss2] += connections[boss1];
            return true;
        }
    }

    bool query(int key1, int key2)
    {
        int boss1 = compressfind(key1);
        int boss2 = compressfind(key2);
        if(boss1 == boss2)
        {
            return true;
        }
        else
        {
            return false;
        }
    }

    int numOfConnector(int key)
    {
        return connections[compressfind(key)];
    }
};

class ConnectingGraph2 {
public:
    unionFind uf;
    ConnectingGraph2(int n) {
        // initialize your data structure here.
        uf.init(n);
    }

    void  connect(int a, int b) {
        // Write your code here
        uf.bossunion(a, b);
    }

    int query(int a) {
        // Write your code here
        return uf.numOfConnector(a);
    }
};