分析
本题考查并查集的运用,分别对行和列都进行并查集操作。
- 首先用一个map把坐标的映射关系设置一下。
- 然后要把行下标从小到大排一遍,进行并查集操作。
- 然后再把列下标从小到大排一遍,进行并查集操作。
- 之后把在同一个集合中的总数记录一下,存放在cnt[]中
C++ 代码
class Solution {
public:
typedef pair<int,int> PII;
int fa[10010],cnt[10010];
map<PII,int> mp; //映射坐标和下标i之间的关系
int ans;
int find(int x) //并查集操作
{
if(fa[x]!=x) fa[x]=find(fa[x]);
return fa[x];
}
bool static cmp1(vector<int> a,vector<int> b) //以行下标从小到大排
{
if(a[0]!=b[0]) return a[0]<b[0];
return a[1]<b[1];
}
bool static cmp2(vector<int> a,vector<int> b) //以列下表从小到大排
{
if(a[1]!=b[1]) return a[1]<b[1];
return a[0]<b[0];
}
int removeStones(vector<vector<int>>& stones) {
int n=stones.size();
if(n<1) return 0;
sort(stones.begin(),stones.end(),cmp1); //第一次排序(行)
for(int i=0;i<n;i++)
{
mp[{stones[i][0],stones[i][1]}]=i; //进行映射
fa[i]=i;
if(i && stones[i][0]==stones[i-1][0]) //行下标相同,并查集操作
{
int faa=find(i),fbb=find(i-1);
fa[faa]=fbb;
}
}
sort(stones.begin(),stones.end(),cmp2); //第二次排序(列)
for(int i=0;i<n;i++)
{
if(i && stones[i][1]==stones[i-1][1]) //列下标相同,并查集操作
{
int faa=find(mp[{stones[i][0],stones[i][1]}]),fbb=find(mp[{stones[i-1][0],stones[i-1][1]}]);
fa[faa]=fbb;
}
}
for(int i=0;i<n;i++) cnt[find(fa[i])]++; //统计同一个连通块中的总个数
for(int i=0;i<10010;i++) ans+=max(0,cnt[i]-1); //加上cnt[i]-1。(4个点只能去掉3个,3个点只能去掉2个,所以要-1)
return ans;
}
};