Problem description:
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?
1
2
3
4
| Example 1:
Input: stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
Output: 5
|
1
2
3
4
| Example 2:
Input: stones = [[0,0],[0,2],[1,1],[2,0],[2,2]]
Output: 3
|
1
2
3
4
| Example 3:
Input: stones = [[0,0]]
Output: 0
|
Note:
1 <= stones.length <= 1000
0 <= stones[i][j] < 10000
Solution:
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
| class Solution {
public:
vector<int> sroot;
int removeStones(vector<vector<int>>& stones) {
int n= stones.size();
sroot= vector<int>(n);
for(int i= 0; i< n; i++)
sroot[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])
Union(i, j);
}
}
int connected= 0;
for(int i= 0; i< n; i++){
if(sroot[i] == i)
connected++;
}
return n-connected;
}
void Union(int i, int j){
sroot[find(i)]= find(j);
}
int find(int i){
return sroot[i] == i? sroot[i]: find(sroot[i]);
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public:
int removeStones(vector<vector<int>>& stones) {
set<vector<int>> visited;
int count= 0;
for(auto stone: stones){
if(!visited.count(stone)){
dfs(stones, visited, stone);
count++;
}
}
return stones.size()-count;
}
void dfs(vector<vector<int>>& stones, set<vector<int>>& visited, vector<int> s1){
visited.insert(s1);
for(auto s2: stones){
if(!visited.count(s2)){
if(s1[0] == s2[0] || s1[1] == s2[1])
dfs(stones, visited, s2);
}
}
}
};
|
time complexity: $O()$
space complexity: $O()$
reference: