題目:
有一個二維的陣列
上面有很多石頭
如果時候在同一排或是同一列
就可以把其中一個拿起來
請問最多可以拿幾個走
思路:
這裡想了一陣子之後覺得應該是圖論
第一個想到的是無向圖的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