number of islands 2

solution

http://www.lintcode.com/en/problem/number-of-islands-ii/

code

/**
 * Definition for a point.
 * struct Point {
 *     int x;
 *     int y;
 *     Point() : x(0), y(0) {}
 *     Point(int a, int b) : x(a), y(b) {}
 * };
 */

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 boss = find(key);

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

        return boss;
    }

    bool bossunion(int s1, int s2)
    {
        int father_s1 = compress_find(s1);
        int father_s2 = compress_find(s2);
        if(father_s1 != father_s2)
        {
            hash[father_s1] = father_s2;
            return true;
        }

        return false;
    }

};

class Solution {
public:
    /**
     * @param n an integer
     * @param m an integer
     * @param operators an array of point
     * @return an integer array
     */
    vector<int> numIslands2(int n, int m, vector<Point>& operators) {
        // Write your code here

        vector<int> ret;
        if(n == 0 || m == 0)
        {
            return ret;
        }

        UnionFind uf(m*n);

        int count = 0;

        int dx[] = {0, 1, 0, -1};
        int dy[] = {1, 0, -1, 0};
        int step = 1;
        for(Point tmp : operators)
        {
            //cout<<"step : "<<step++<<endl;
            //cout<<tmp.x<<" "<<tmp.y<<endl;
            count++;
            //cout<<count<<endl;
            int id = tmp.x * m + tmp.y;
            uf.change(id, id);
            for(int i = 0; i<4; i++)
            {
                int nx = tmp.x + dx[i];
                int ny = tmp.y + dy[i];
                int nextid = nx*m+ny;
                if(nx < 0 || nx >= n || ny < 0 || ny >= m || uf.find(nextid) == -1)
                {
                    continue;
                }

                //如果合并成功（两者原先不在一个集合），count--
                //如果合并失败（两者已经在一个集合），count不变
                if(uf.bossunion(id, nextid))
                {
                    count--;
                }

            }
            ret.push_back(count);
        }

        return ret;
    }
};