1. 数岛屿问题
如果两个石头在同行或者同列，两个石头就是连接的。连在一起的石头，可以组成一个连通图。每一个连通图至少会剩下1个石头。
所以我们希望存在一种思路，每个连通图都只剩下1个石头。
这样这题就转化成了数岛屿的问题。
2. 朴素DFS
实际上做这道题，你并不需要去构造或者证明，移走石头的方案。有了step1里的思路，已经足够用dfs来解决这个问题了。
def removeStones(self, points):
rows = collections.defaultdict(set)
cols = collections.defaultdict(set)
for i, j in points:
rows[i].add(j)
cols[j].add(i)
def dfsRow(i):
seenR.add(i)
for j in rows[i]:
if j not in seenC:
dfsCol(j)
def dfsCol(j):
seenC.add(j)
for i in cols[j]:
if i not in seenR:
dfsRow(i)
seenR, seenC = set(), set()
islands = 0
for i, j in points:
if i not in seenR:
islands += 1
dfsRow(i)
dfsCol(j)
return len(points) - islands
3. 优化行列处理
上述代码有很多冗余，实际上我们对行列的搜索，没有任何本质区别。
只不过是因为同一个index，可能是行也可能是列，所以我们做了区分。
实际上，只要我们能区分行列的index，代码就可以缩减一半了。
行的index我们还可以用0～N - 1，列的index我们使用N～2N-1就可以了。
def removeStones(self, points):
index = collections.defaultdict(set)
for i, j in points:
index[i].add(j + 10000)
index[j + 10000].add(i)
def dfs(i):
seen.add(i)
for j in index[i]:
if j not in seen:
dfs(j)
seen = set()
islands = 0
for i, j in points:
if i not in seen:
islands += 1
dfs(i)
dfs(j + 10000)
return len(points) - islands
4. 换个思考角度
我们之前的思路是，对石头所在point进行搜索。
有了以上代码，我们就会发现，其实我们搜索的元素是行列的index。
我们以为是行列把石头连接在了一起。
换个角度思考，也可以是一个石头把它所在行列坐标连在了一起。
我们的输入是所有的石头，每个石头都固定连接两个元素。
想到这里，union find的思路就已经呼之欲出了。
C++:
int removeStones(vector<vector<int>>& stones) {
for (int i = 0; i < stones.size(); ++i)
uni(stones[i][0], ~stones[i][1]);
return stones.size() - islands;
}
unordered_map<int, int> f;
int islands = 0;
int find(int x) {
if (!f.count(x)) f[x] = x, islands++;
if (x != f[x]) f[x] = find(f[x]);
return f[x];
}
void uni(int x, int y) {
x = find(x), y = find(y);
if (x != y) f[x] = y, islands--;
}
Java:
Map<Integer, Integer> f = new HashMap<>();
int islands = 0;
public int removeStones(int[][] stones) {
for (int i = 0; i < stones.length; ++i)
union(stones[i][0], ~stones[i][1]);
return stones.length - islands;
}
public int find(int x) {
if (f.putIfAbsent(x, x) == null)
islands++;
if (x != f.get(x))
f.put(x, find(f.get(x)));
return f.get(x);
}
public void union(int x, int y) {
x = find(x);
y = find(y);
if (f.get(x) != y) {
f.put(find(x), find(y));
islands--;
}
}
Python:
def removeStones(self, points):
UF = {}
def find(x):
if x != UF[x]:
UF[x] = find(UF[x])
return UF[x]
def union(x, y):
UF.setdefault(x, x)
UF.setdefault(y, y)
UF[find(x)] = find(y)
for i, j in points:
union(i, ~j)
return len(points) - len({find(x) for x in UF})
5. 构造移走石头方案
逆向思维，来看一下，如果开始只有一个石头，每次都只能放一个新石头在同行或同列，我们能否构造出整个岛屿。
还是不难得，可以用dfs里查找石头的顺序放，就可以构造整个岛屿了。
反之，按照反序也可以移走整个岛屿直到剩下一个石头。
