947. Most Stones Removed with Same Row or Column

On a 2D plane, we place stones at some integer coordinate points. Each coordinate point may have at most one stone.

Now, a move consists of removing a stone that shares a column or row with another stone on the grid.

What is the largest possible number of moves we can make?

Example 1:

Input: stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
Output: 5

Example 2:

Input: stones = [[0,0],[0,2],[1,1],[2,0],[2,2]]
Output: 3

Example 3:

Input: stones = [[0,0]]
Output: 0

Note:

1. 1 <= stones.length <= 1000

2. 0 <= stones[i][j] < 10000

// DFS
void dfs(vector<vector<int> >& index, unordered_set<int>& visited, int i) {
    if (visited.count(i)) return;
    visited.insert(i);
    for (int j : index[i]) {
        if (visited.count(j)) continue;
        dfs(index, visited, j);
    }
}
int removeStones(vector<vector<int>>& stones) {
    // Trick to differentiate row id and col id
    const int k = 10000;
    vector<vector<int> > index(2 * k);
    for (const vector<int>& stone : stones) {
        index[stone[0]].push_back(stone[1] + k);
        index[stone[1] + k].push_back(stone[0]);
    }
    unordered_set<int> visited;
    int islands = 0;
    for (const vector<int>& stone : stones) {
        if (visited.count(stone[0])) continue;
        ++islands;
        dfs(index, visited, stone[0]);
        dfs(index, visited, stone[1] + k);
    }
    return stones.size() - islands;
}

// Union-Find
int find(vector<int>& roots, int i) {
    return roots[i] == i ? i : roots[i] = find(roots, roots[i]);
}
void uni(vector<int>& roots, int x, int y) {
    x = find(roots, x), y = find(roots, y);
    if (x != y) {
        roots[y] = x;
    }
}
int removeStones(vector<vector<int>>& stones) {
    const int k = 10000;
    vector<int> roots(2 * k);
    for (int i = 0; i < roots.size(); ++i) roots[i] = i;
    for (const vector<int>& stone : stones) {
        uni(roots, stone[0], stone[1] + k);
    }
    unordered_set<int> islands;
    for (const vector<int>& stone : stones) {
        islands.insert(find(roots, stone[0]));
    }
    return stones.size() - islands.size();
}

// Union-Find
int find(vector<int>& roots, int i) {
    return roots[i] == i ? i : roots[i] = find(roots, roots[i]);
}
void connect(vector<int>& roots, int i, int j) {
    roots[find(roots, j)] = find(roots, i);
}
int removeStones(vector<vector<int>>& stones) {
    const int n = stones.size();
    vector<int> roots(n);
    for (int i = 0; i < n; ++i) roots[i] = i;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            if (stones[i][0] == stones[j][0] || stones[i][1] == stones[j][1]) {
                connect(roots, i, j);
            }
        }
    }
    int cnt = 0;
    for (int i = 0; i < n; ++i) {
        if (roots[i] == i) ++cnt;
    }
    return n - cnt;
}