Union Find

305 Number of Islands II

A 2d grid map of m rows and n columns is initially filled with water. We may perform an addLand operation which turns the water at position (row, col) into a land. Given a list of positions to operate, count the number of islands after each addLand operation. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example:

Given m = 3, n = 3, positions = [[0,0], [0,1], [1,2], [2,1]]. Initially, the 2d grid grid is filled with water. (Assume 0 represents water and 1 represents land).

0 0 0
0 0 0
0 0 0

Operation #1: addLand(0, 0) turns the water at grid[0][0] into a land.

1 0 0
0 0 0   Number of islands = 1
0 0 0

Operation #2: addLand(0, 1) turns the water at grid[0][1] into a land.

1 1 0
0 0 0   Number of islands = 1
0 0 0

Operation #3: addLand(1, 2) turns the water at grid[1][2] into a land.

1 1 0
0 0 1   Number of islands = 2
0 0 0

Operation #4: addLand(2, 1) turns the water at grid[2][1] into a land.

1 1 0
0 0 1   Number of islands = 3
0 1 0

We return the result as an array: [1, 1, 2, 3]

Challenge:

Can you do it in time complexity O(k log mn), where k is the length of the positions?

class UnionFind {
public:
    UnionFind(int n) : size(n), id(n, -1), count(0){}

    int find(int i) {
        if (i != id[i]) id[i] = find(id[i]);
        return id[i];
    }

    void combine(int i, int j) {
        int id1 = find(i);
        int id2 = find(j);
        if (id1 == id2) return;
        if (size[id1] > size[id2]) {
            id[id2] = id1;
            size[id1] += size[id2];
        } else {
            id[id1] = id2;
            size[id2] += size[id1];
        }
        --count;
    }

    int getCount() {return count;}

    void addElement(int i) {
        if (id[i] == -1) {
            id[i] = i;
            count++;
        }
    }

private:
    vector<int> size;
    vector<int> id;
    int count;
};

class Solution {
public:
    vector<int> numIslands2(int m, int n, vector<pair<int, int>>& positions) {
        vector<int> res;
        UnionFind uf(m*n);
        vector<vector<int>> board(m, vector<int>(n));
        vector<int> steps{0, 1, 0, -1, 0};
        for (auto p : positions) {
            uf.addElement(p.first*n + p.second);
            board[p.first][p.second] = 1;
            for (int k = 0; k < steps.size() - 1; ++k) {
                int x = p.first + steps[k];
                int y = p.second + steps[k+1];
                if (x >= 0 && x < m && y >= 0 && y < n && board[x][y]) uf.combine(p.first*n + p.second, x*n +y);
            }
            res.push_back(uf.getCount());
        }
        return res;
    }
};

Group Contacts

有这么一个class Contact，里面有一个string的name，和一个vector 装着email address，是这个Contact有的address，用一个list装着是因为一个人有可 能有多个email，现在给你vector，比如

{
    { "John", {"[email protected]"} },
    { "Mary", {"[email protected]"} },
    { "John", {"[email protected]"} },
    { "John", {"[email protected]", "[email protected]", "[email protected]"} },
    { "Bob",  {"[email protected]"} }
}

现在我们知道如果email address相同的话，那么就说明是同一个人，现在要做的是根据这些email address，把同一个contact给group起来，生成一个vector>

class Contact {
public:
    string name;
    vector<string> emails;
};
class UnionFind {
    vector<int> father, ranks;
public:
    UnionFind(int num_nodes) {
        for (int i = 0; i < num_nodes; i++) {
            father.push_back(i);
            ranks.push_back(0);
        }
    }
    int find(int x) {
        if (x == father[x]) return x;
        return father[x] = find(father[x]);
    }
    void do_union(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) return;
        if (ranks[x] < ranks[y]) {
            father[x] = y;
        } else {
            father[y] = x;
            if (ranks[x] == ranks[y]) {
                ranks[x]++;
            }
        }
    }
};
vector<vector<Contact>> group_contacts(vector<Contact>& input) {
    unordered_map<string,vector<int>> email_record;

    int n = (int)input.size();
    for (int k = 0; k < input.size(); k++) {
        for (auto email : input[k].emails) {
            email_record[email].push_back(k);
        }
    }
    UnionFind uf(n);
    for (auto p : email_record) {
        for (int i = 0; i < p.second.size() - 1; i++) {
            uf.do_union(p.second[i], p.second[i + 1]);
        }
    }
    unordered_map<int,vector<int>> groups;
    for (int i = 0; i < n; i++) groups[uf.find(i)].push_back(i);

    vector<vector<Contact>> ret;
    for (auto& p : groups) {
        vector<Contact> vs;
        for (auto& c : p.second) vs.push_back(input[c]);
        ret.push_back(vs);
    }
    return ret;
}