GeeksforGeeks-Solution/src/Maximum Stone Removal/Code/solution.cpp at main · withaarzoo/GeeksforGeeks-Solution · GitHub

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
class DSU
{
public:
    vector<int> parent, rankv;

    DSU(int n)
    {
        parent.resize(n);
        rankv.assign(n, 0);
        for (int i = 0; i < n; ++i)
            parent[i] = i;
    }

    int find(int x)
    {
        // Path compression
        if (parent[x] != x)
            parent[x] = find(parent[x]);
        return parent[x];
    }

    void unite(int a, int b)
    {
        a = find(a);
        b = find(b);
        if (a == b)
            return;

        // Union by rank
        if (rankv[a] < rankv[b])
        {
            parent[a] = b;
        }
        else if (rankv[b] < rankv[a])
        {
            parent[b] = a;
        }
        else
        {
            parent[b] = a;
            rankv[a]++;
        }
    }
};

class Solution
{
public:
    int maxRemove(vector<vector<int>> &stones)
    {
        int n = stones.size();
        DSU dsu(n);

        unordered_map<int, int> rowRep;
        unordered_map<int, int> colRep;

        for (int i = 0; i < n; ++i)
        {
            int r = stones[i][0];
            int c = stones[i][1];

            if (rowRep.count(r))
            {
                dsu.unite(i, rowRep[r]);
            }
            else
            {
                rowRep[r] = i;
            }

            if (colRep.count(c))
            {
                dsu.unite(i, colRep[c]);
            }
            else
            {
                colRep[c] = i;
            }
        }

        int components = 0;
        for (int i = 0; i < n; ++i)
        {
            if (dsu.find(i) == i)
                components++;
        }
        return n - components;
    }
};