LeetCode 947. Most Stones Removed with Same Row or Column

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int removeStones(vector<vector<int>>& stones) {
        const int n = stones.size();
        vector<vector<int>> edges(n);
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                if ((stones[i][0] == stones[j][0]) || (stones[i][1] == stones[j][1]))
                    edges[i].emplace_back(j);
        vector<bool> visited(n);
        function<void(int)> dfs = [&](int x) {
            visited[x] = true;
            for (const int y : edges[x])
                if (!visited[y])
                    dfs(y);
        };
        int cnt = 0;
        for (int i = 0; i < n; ++i)
            if (!visited[i]) {
                ++cnt;
                dfs(i);
            }
        return n - cnt;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    int removeStones(vector<vector<int>>& stones) {
        const int n = stones.size();
        unordered_map<int, vector<int>> m;
        for (int i = 0; i < n; ++i) {
            m[stones[i][0]].emplace_back(i);
            m[stones[i][1] + 10000].emplace_back(i);
        }
        vector<vector<int>> edges(n);
        for (const auto& [_, vec] : m) {
            const int k = vec.size();
            for (int i = 1; i < k; ++i) {
                edges[vec[i - 1]].emplace_back(vec[i]);
                edges[vec[i]].emplace_back(vec[i - 1]);
            }
        }
        vector<bool> visited(n);
        function<void(int)> dfs = [&](int x) {
            visited[x] = true;
            for (const int y : edges[x])
                if (!visited[y])
                    dfs(y);
        };
        int cnt = 0;
        for (int i = 0; i < n; ++i)
            if (!visited[i]) {
                ++cnt;
                dfs(i);
            }
        return n - cnt;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class DisjointSetUnion {
private:
    unordered_map<int, int> f, rank;
public:
    int find(int x) {
        if (f.find(x) == f.end()) {
            f[x] = x;
            rank[x] = 1;
        }
        return f[x] == x ? x : f[x] = find(f[x]);
    }
    void unionSet(int x, int y) {
        int fx = find(x), fy = find(y);
        if (fx != fy) {
            if (rank[fx] > rank[fy])
                swap(fx, fy);
            rank[fy] += rank[fx];
            f[fx] = fy;
        }
    }
    int numberOfConnectedComponent() {
        int cnt = 0;
        for (auto &[x, fa] : f)
            if (x == fa)
                ++cnt;
        return cnt;
    }
};
class Solution {
public:
    int removeStones(vector<vector<int>> &stones) {
        const int n = stones.size();
        DisjointSetUnion dsu;
        for (int i = 0; i < n; ++i)
            dsu.unionSet(stones[i][0], stones[i][1] + 10000);
        return n - dsu.numberOfConnectedComponent();
    }
};