一道图上的并查集题目，思路和实现都很简单，不过还是很巧妙

<h1 id="leetcode-947-">LeetCode 947. 移除最多的同行或同列石头</h1>
<h2 id="heading">题目描述</h2>
<math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>n</mi></mrow><annotation encoding="application/x-tex">n</annotation></semantics></math>n 块石头放置在二维平面中的一些整数坐标点上。每个坐标点上最多只能有一块石头。
如果一块石头的 同行或者同列 上有其他石头存在，那么就可以移除这块石头。
给你一个长度为 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>n</mi></mrow><annotation encoding="application/x-tex">n</annotation></semantics></math>n 的数组 <code>stones</code> ，其中 <code>stones[i] = [xi, yi]</code> 表示第 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>i</mi></mrow><annotation encoding="application/x-tex">i</annotation></semantics></math>i 块石头的位置，返回 可以移除的石子 的最大数量。
示例 1
输入：<code>stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]</code> 
输出：<code>5</code> 
解释：
<pre style="background-color:#fff">一种移除 5 块石头的方法如下所示：
1. 移除石头 [2,2] ，因为它和 [2,1] 同行。
2. 移除石头 [2,1] ，因为它和 [0,1] 同列。
3. 移除石头 [1,2] ，因为它和 [1,0] 同行。
4. 移除石头 [1,0] ，因为它和 [0,0] 同列。
5. 移除石头 [0,1] ，因为它和 [0,0] 同行。
石头 [0,0] 不能移除，因为它没有与另一块石头同行/列。
</pre>示例 2
输入：<code>stones = [[0,0],[0,2],[1,1],[2,0],[2,2]]</code> 
输出：<code>3</code> 
解释：
<pre style="background-color:#fff">一种移除 3 块石头的方法如下所示：
1. 移除石头 [2,2] ，因为它和 [2,0] 同行。
2. 移除石头 [2,0] ，因为它和 [0,0] 同列。
3. 移除石头 [0,2] ，因为它和 [0,0] 同行。
石头 [0,0] 和 [1,1] 不能移除，因为它们没有与另一块石头同行/列。
</pre>示例 3
输入：<code>stones = [[0,0]]</code> 
输出：<code>0</code> 
解释：
<pre style="background-color:#fff">[0,0] 是平面上唯一一块石头，所以不可以移除它。
</pre><h2 id="heading-1">题解</h2>
题目意思是，如果同一行或同一列有多个石头，那么可以“消去”其他石头只留下一个，求最多能消去多少个。
首先进行名词定义：
<ul>
<li>关系: 两个石头在同一行和同一列，则说明这两个石头存在关系</li>
<li>弱关系: 两个石头不在同一行和同一列，但是可以通过多个关系的传递，实现弱关系</li>
<li>同类: 所有具有弱关系的石头分类</li>
<li>消去: 如果两个石头具有关系，那么可以从图上删除其中一个石头</li>
</ul>
首先举一个简单的例子，如图，<math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>0</mn></mrow><annotation encoding="application/x-tex">0</annotation></semantics></math>0 和 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>1</mn></mrow><annotation encoding="application/x-tex">1</annotation></semantics></math>1 在同一行，<math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>0</mn></mrow><annotation encoding="application/x-tex">0</annotation></semantics></math>0 和 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>2</mn></mrow><annotation encoding="application/x-tex">2</annotation></semantics></math>2 在同一列，并且在这种“消去”时，应该先消去 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>1</mn></mrow><annotation encoding="application/x-tex">1</annotation></semantics></math>1 或 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>2</mn></mrow><annotation encoding="application/x-tex">2</annotation></semantics></math>2，再消去 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>0</mn></mrow><annotation encoding="application/x-tex">0</annotation></semantics></math>0。 
也即最多可以消去 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>2</mn></mrow><annotation encoding="application/x-tex">2</annotation></semantics></math>2 个
<?xml version="1.0" encoding="UTF-8" standalone="no"?>
<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN"
 "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd">


<svg width="134pt" height="116pt"
 viewBox="0.00 0.00 134.00 116.00" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink">
<g id="graph0" class="graph" transform="scale(1 1) rotate(0) translate(4 112)">
<title>%3</title>
<polygon fill="#ffffff" stroke="transparent" points="-4,4 -4,-112 130,-112 130,4 -4,4"/>

<g id="node1" class="node">
<title>0</title>
<ellipse fill="none" stroke="#000000" cx="27" cy="-90" rx="27" ry="18"/>
<text text-anchor="middle" x="27" y="-86.3" font-family="Times,serif" font-size="14.00" fill="#000000">0</text>
</g>

<g id="node2" class="node">
<title>1</title>
<ellipse fill="none" stroke="#000000" cx="99" cy="-90" rx="27" ry="18"/>
<text text-anchor="middle" x="99" y="-86.3" font-family="Times,serif" font-size="14.00" fill="#000000">1</text>
</g>

<g id="edge1" class="edge">
<title>0&#45;&#45;1</title>
<path fill="none" stroke="#000000" d="M54,-90C59.9766,-90 65.9531,-90 71.9297,-90"/>
</g>

<g id="node3" class="node">
<title>2</title>
<ellipse fill="none" stroke="#000000" cx="27" cy="-18" rx="27" ry="18"/>
<text text-anchor="middle" x="27" y="-14.3" font-family="Times,serif" font-size="14.00" fill="#000000">2</text>
</g>

<g id="edge2" class="edge">
<title>0&#45;&#45;2</title>
<path fill="none" stroke="#000000" d="M27,-71.8314C27,-61 27,-47.2876 27,-36.4133"/>
</g>
</g>
</svg>
看到这道题的思路是：把所有同一行同一列的分成一类，然后从“边缘”开始删，直到删到不能再删
如果所有的石头都具有关系，那么显然可以直接消去至只剩下一个。 
如果石头之间存在弱关系，可以先消去边缘（只和一个石头存在关系）的石头，重复该过程直到剩下的石头都和多于一个的石头存在关系。 
如果将关系以连线表示，说明这时石头之间“成环”。由于环中所有石头都拥有两个以上的关系，因此每一个石头仍然保持可消去的特点，只需要考虑会不会存在任意选的石头，把原本的一个分类划分成两个分类，导致这种情况的原因是多个环共用一个石头，删去该石头后多个环弱连接丧失。 
但同理也可反推，只需要保持这个石头存在，那么所有的环都可被消去。 
更复杂的情况也可简化至这种情况。
于是，可以得到结论：同类的石头，必定可以被消去至只剩一个
也即，在消去至只剩下一个的情况中，弱关系 和 关系 等价。
那么只需要将所有的石头进行分类即可，每个分类留一个就是最后剩余的石头。
求 事物之间存在连接和弱连接关系 使用 并查集
<hr>
这道题最大的意义是，确定 并查集 的使用情景，在遇到 弱连接分类问题 时，就可以尝试一下
附上并查集核心代码
<pre style="background-color:#fff">f = [i for i in range(n)]
def getF(x):
 &#39;&#39;&#39;
 获得 x 所在分类的代表
 带路径压缩，尽可能使得每个元素都直指代表
 &#39;&#39;&#39;
 f[x] = x if f[x] == x else getF(f[x])
 return f[x]
def connect(i, j):
 &#39;&#39;&#39;
 i 和 j 存在弱连接
 &#39;&#39;&#39;
 f[getF(i)] = getF(j)
</pre><h2 id="heading-2">代码</h2>
<pre style="background-color:#fff">class Solution:
 def removeStones(self, stones: List[List[int]]) -&gt; int:
 n = len(stones)
 f = [i for i in range(n)]
 def getF(x):
 f[x] = x if f[x] == x else getF(f[x])
 return f[x]
 def connect(i, j):
 f[getF(i)] = getF(j)
 
 dx = {}
 dy = {}
 for i, stone in enumerate(stones):
 x, y = stone

 sx = dx.get(x, None)
 if sx == None:
 dx[x] = i
 else:
 connect(i, sx)
 
 sy = dy.get(y, None)
 if sy == None:
 dy[y] = i
 else:
 connect(i, sy)
 
 count = 0
 for i in range(n):
 if getF(i) == i:
 count += 1

 return n - count
</pre>