移除最多的同行或同列石头

Leetcode题目链接

描述

详见中文题目链接。

解答

class Solution {
private:
    unordered_map<int, int> rowFirst, columnFirst;
    vector<int> p;
    int sets;

    void build(int n) {
        for (int i = 0; i < n; i++) p.emplace_back(i);
        sets = n;
    }

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

    void unionSets(int x, int y) {
        int fx = find(x), fy = find(y);
        if (fx != fy) {
            p[fx] = fy;
            sets--;
        }
    }

public:
    int removeStones(vector<vector<int>>& stones) {
        int n = stones.size();
        build(n);

        for (int i = 0; i < n; i++) {
            int row = stones[i][0], col = stones[i][1];
            if (!rowFirst.count(row))
                rowFirst[row] = i;
            else
                unionSets(i, rowFirst[row]);

            if (!columnFirst.count(col))
                columnFirst[col] = i;
            else
                unionSets(i, columnFirst[col]);
        }

        return n - sets;
    }
};