題目
分析
乍看之下，有點摸不著頭腦捏检。稍微舉幾個簡單的例子荞驴，就能發(fā)現(xiàn)其中的規(guī)律。
題目給出一個“相連”的概念贯城，即行或者列相同熊楼，這里可以用坐標系來理解。
那么能犯，首先分析一些基本情況：
- 當沒有石頭“相連”鲫骗，那么無法做出符合題意的操作，是0踩晶；
- 只有2個石頭“相連”执泰，能做出1個操作；
- 3個石頭“相連”合瓢，就是2個操作坦胶；
- 可見，如果一組有n個石頭相連晴楔，那么操作數(shù)就是n-1顿苇；
- 假如有兩組，一組2相連税弃，一組3相連纪岁，它們互相之間并不干涉，最后結果就是分別能進行操作的數(shù)目相加则果；
- 假設總共有m個互不干涉的組幔翰，那么操作數(shù)總共就是
(n(0)-1)+(n(1)-1)+...+(n(m-1)-1)，其中n(i)代表第i組的石頭個數(shù)西壮。因為總共的石頭個數(shù)是給定的遗增，假設為N，那么可得最后的操作數(shù)就是(n(0)+...+n(m-1))-m = N-m款青。也就是說做修，問題轉化為求總共有多少個互不相干的組。 - 要解決這個問題，連通圖就是一個很直接的想法饰及。但問題來了蔗坯，我們一般運用的連通圖是1維的，這個是2維的燎含，怎么弄宾濒？假如強行開2維連通圖，需要解決很多小問題屏箍，不是一時半會能寫出無bug代碼的绘梦，因此不如嘗試把2維轉化為1維。
- 根據(jù)題意铣除，坐標的x和y是需要區(qū)分開來的谚咬，因為兩個石頭(x1,y1)與(x2,y2)，x或者y相等屬于相連尚粘，但x1=y2這種可不算择卦。
- 最簡潔的做法，就是把y加上一個值郎嫁，讓x和y不會重合就好秉继。題目里給的值是10000.
- 構造圖只需要連通單個石頭本身的x與y+10000就行了。假如與之前某個石頭“相連”泽铛，連通的時候自然會發(fā)現(xiàn)尚辑。
- 到這里，問題就解決了盔腔，參考代碼如下：
// T:O(NlogN) S:O(N)
class Solution {
public int removeStones(int[][] stones) {
int N = stones.length;
DSU dsu = new DSU(20000);
for (int[] stone: stones)
dsu.union(stone[0], stone[1] + 10000);
Set<Integer> seen = new HashSet();
for (int[] stone: stones)
seen.add(dsu.find(stone[0]));
return N - seen.size();
}
}
class DSU {
int[] parent;
public DSU(int N) {
parent = new int[N];
for (int i = 0; i < N; ++i)
parent[i] = i;
}
public int find(int x) {
if (parent[x] != x) parent[x] = find(parent[x]);
return parent[x];
}
public void union(int x, int y) {
parent[find(x)] = find(y);
}
}
