题目:
有一个二维的阵列
上面有很多石头
如果时候在同一排或是同一列
就可以把其中一个拿起来
请问最多可以拿几个走
思路:
这里想了一阵子之后觉得应该是图论
第一个想到的是无向图的khan的那种方法
从最无关的石头开始拿
拿到最后的那个最多石头交集的石头
但是问题是
我要怎么判定石头的rank?
如果他们有交集 他们的rank就会一样
那我要从那个开始?
所以这个方法不行
然后发呆一下
就想到
如果他们是有交集的那群
那其实永远都可以拿到只剩最后一颗石头
只要确保那群之间全部都可以交集在一起就好
那就是unionfind 了
然后要对每颗石头每种交集检查
所以用n^2的时间
1000^2会过
之后因为一次最多丢一颗石头
慢慢纪录然后就好ㄌ
然后我很少写union find 所以好像有点怪
```cpp
typedef struct rock{
int x;
int y;
}rock;
class Solution {
public:
int res ;
vector<int> num;
int find(int x)
{
if(num[x] == x)return x;
num[x] = find(num[x]);
return num[x];
}
void onion(int i , int j)
{
int in = find(i);
int jn = find(j);
if(in == jn)return;
if(in < jn)num[jn] = in;
else num[in] = jn;
}
int removeStones(vector<vector<int>>& stones)
{
int n = stones.size();
res = n;
num.resize(n);
for(int i = 0 ; i < n ; i ++)num[i] = i;
for(int i = 0 ; i < n ; i ++)
{
for(int j = i+1 ; j < n ; j ++)
{
if(stones[i][0] == stones[j][0] || stones[i][1] == stones[j][1])
{
if(find(i) != find(j))
{
onion(i,j);
res