题目:
947. Most Stones Removed with Same Row or Column:
给你一个二维矩阵mx，mx[i][0],mx[i][1]代表这边有一颗石头，今天在任一row/column上
如果有两颗以上的石头，我们可以任意移除直到该row/column上只剩一颗石头，求我们
最大的可能石头移除量
思路:
第一眼看到就可以很明确知道这是找compoment数目的题目，所以可以用union find
或是dfs找，但本来一想到mx[i][0]<=10**4，但mx.size()<1000，所以应该用mx[i]当基底
而不是开一个10**4长度的vector做union，结果爆烂，用mx[i][0]当基底才是正解
int removeStones(vector<vector<int>>& stones) {
vector<vector<set<int>>> pre_ans;
vector<int> ans;
vector<int> sugar;
for(int i=0;i<stones.size();++i){
if(pre_ans.empty()){
set<int> paper1;
set<int> paper2;
paper1.insert(stones[i][0]);
paper2.insert(stones[i][1]);
pre_ans.push_back({paper1,paper2});
ans.push_back(0);
sugar.push_back(0);
}
else{
bool lokfor=true;
int prelab;
for(int j=0;j<pre_ans.size();++j){
if((pre_ans[j][0].count(stones[i][0]) ||
pre_ans[j][1].count(stones[i][1])) &&lokfor){
if(sugar[j]==j){
prelab=j;
pre_ans[j][0].insert(stones[i][0]);
pre_ans[j][1].insert(stones[i][1]);
ans[j]++;
lokfor=false;
}
else{
int prelab=sugar[j];
pre_ans[prelab][0].insert(stones[i][0]);
pre_ans[prelab][1].insert(stones[i][1]);
ans[prelab]++;
lokfor=false;
}
}
else if((pre_ans[j][0].count(stones[i][0]) ||
pre_ans[j][1].count(stones[i][1])) && !lokfor){
if(sugar[j]==j){
sugar[j]=prelab;
for(auto &h: pre_ans[j][0]){
pre_ans[prelab][0].insert(h);
}
for(auto &h:pre_ans[j][1]){
pre_ans[prelab][1].insert(h);
}
ans[prelab]+=(ans[j]+1);
pre_ans[prelab][0].insert(stones[i][0]);
pre_ans[prelab][1].insert(stones[i][1]);
ans[j]=-1;
pre_ans[j][0].clear();
pre_ans[j][1].clear();
}
}
}
if(lokfor){
set<int> paper1;
set<int> paper2;
paper1.insert(stones[i][0]);
paper2.insert(stones[i][1]);
pre_ans.push_back({paper1,paper2});
ans.push_back(0);
int yo=sugar.size();
sugar.push_back(yo);
}
}
}
int ola=0;
for(auto h:ans){
if(h!=-1){
ola+=h;
}
}
return ola;
}