題目: 有一個二維的陣列 上面有很多石頭 如果時候在同一排或是同一列 就可以把其中一個拿起來 請問最多可以拿幾個走 思路: 這裡想了一陣子之後覺得應該是圖論 第一個想到的是無向圖的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--; } } } } return n-res; } }; ``` -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.162.9.21 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1724902491.A.B05.html