联合查找 python3
Union find in python3
我知道如何实现 union find 一般，但我在想是否有办法利用 python 中的集合结构来实现相同的结果。
例如，我们可以很容易地合并集合。但是我不确定如何仅使用集合来确定两个元素是否在同一集合中。
所以，我想知道 python 中是否有支持这种操作的数据结构，而不是通常的实现？
你想要这样的东西吗？
myset = ...
all(elt in myset for elt in (a,b))
你总是可以解决这个问题，方法是将它想象成一棵树，它的节点通过根相互连接，如果你想知道两个节点是否连接，然后查找树。如果您要比较的两个节点具有相同的根（它们在同一棵树中），则它们是连接的。
要连接两个节点，只需转到它们所在的每棵树的根，并使一个根成为另一个的父节点。
这个视频会给你一个很好的直觉：
https://www.youtube.com/watch?v=YIFWCpquoS8&list=PLUX6FBiUa2g4YWs6HkkCpXL6ru02i7y3Q&index=1
树节点之间的连接可以通过支持它的语言中的指针来建立，但是如果你的语言不支持它（python），那么你可以通过存储位置和链接来创建自己的指针数组。
数组的位置代表您的节点，其中的值代表特定节点与其根的连接。一开始，数组中的位置用节点号填充，因为节点最初没有父节点，但是当你连接节点时，根发生变化，数组必须表示这一点。实际上，存储在那里的值是根的标识符。
但首先尝试将问题视觉化，而不是考虑数组和过多的数学技巧。直观地处理它会使解决方案听起来很平庸，并且可以在编写代码时提供很好的指导。
我这么说是因为我看过我刚刚发布的 Robert Sedgewick 的视频，其中包含解决方案的图形模拟，并在没有过多关注他书中的代码的情况下实现了自己。视频给我的直觉比任何数学都有价值。
它会帮你把节点封装成一个class，方法如下：
- climbTreeFromNodeUpToRoot
- setNewParentToThisNodeAndUpdateHeights
第一种方法，顾名思义，从一个节点开始，沿着树向上走，直到找到它的根，然后返回。
如果你用这个方法比较两个节点（实际上是它返回的根），你可以很容易地通过比较它们的根来知道它们是否连接。
一旦你想把它们连接起来，你就上两个节点的树，让一个根以另一个为父节点。
树可以长得很高（抱歉，我没有使用官方命名法，但这对我来说很有意义），所以当你必须爬树时，这种简单的方法会变得非常慢稍后。
为防止树变高，请不要无条件地将一个根作为另一个根的父根，而是附上最小的棵树（根据高度，而不是数量元素）到最高的。
为此，您需要知道每棵树的高度，并且您可以将此信息存储在它们各自的根上（在您的情况下通过额外的数组，或者在其他语言中通过每个节点的额外指针）。每当另一棵树连接到它时，都应该更新此信息。
一棵树不可能知道她刚刚连接了一棵新树，因此重要的是每棵连接到第二棵树的树都会通知第二棵树更新其高度。
这个信息可以传给第二棵树的根，以后用来判断（如前所述）哪棵树是最小的。请记住，将一棵小树连接到一棵大树而不是相反的大树会为您节省大量时间。
我知道如何实现 union find 一般，但我在想是否有办法利用 python 中的集合结构来实现相同的结果。 例如，我们可以很容易地合并集合。但是我不确定如何仅使用集合来确定两个元素是否在同一集合中。 所以，我想知道 python 中是否有支持这种操作的数据结构，而不是通常的实现？
你想要这样的东西吗？
myset = ...
all(elt in myset for elt in (a,b))
你总是可以解决这个问题，方法是将它想象成一棵树，它的节点通过根相互连接，如果你想知道两个节点是否连接，然后查找树。如果您要比较的两个节点具有相同的根（它们在同一棵树中），则它们是连接的。
要连接两个节点，只需转到它们所在的每棵树的根，并使一个根成为另一个的父节点。
这个视频会给你一个很好的直觉： https://www.youtube.com/watch?v=YIFWCpquoS8&list=PLUX6FBiUa2g4YWs6HkkCpXL6ru02i7y3Q&index=1
树节点之间的连接可以通过支持它的语言中的指针来建立，但是如果你的语言不支持它（python），那么你可以通过存储位置和链接来创建自己的指针数组。
数组的位置代表您的节点，其中的值代表特定节点与其根的连接。一开始，数组中的位置用节点号填充，因为节点最初没有父节点，但是当你连接节点时，根发生变化，数组必须表示这一点。实际上，存储在那里的值是根的标识符。
但首先尝试将问题视觉化，而不是考虑数组和过多的数学技巧。直观地处理它会使解决方案听起来很平庸，并且可以在编写代码时提供很好的指导。
我这么说是因为我看过我刚刚发布的 Robert Sedgewick 的视频，其中包含解决方案的图形模拟，并在没有过多关注他书中的代码的情况下实现了自己。视频给我的直觉比任何数学都有价值。
它会帮你把节点封装成一个class，方法如下：
- climbTreeFromNodeUpToRoot
- setNewParentToThisNodeAndUpdateHeights
第一种方法，顾名思义，从一个节点开始，沿着树向上走，直到找到它的根，然后返回。
如果你用这个方法比较两个节点（实际上是它返回的根），你可以很容易地通过比较它们的根来知道它们是否连接。
一旦你想把它们连接起来，你就上两个节点的树，让一个根以另一个为父节点。
树可以长得很高（抱歉，我没有使用官方命名法，但这对我来说很有意义），所以当你必须爬树时，这种简单的方法会变得非常慢稍后。
为防止树变高，请不要无条件地将一个根作为另一个根的父根，而是附上最小的棵树（根据高度，而不是数量元素）到最高的。
为此，您需要知道每棵树的高度，并且您可以将此信息存储在它们各自的根上（在您的情况下通过额外的数组，或者在其他语言中通过每个节点的额外指针）。每当另一棵树连接到它时，都应该更新此信息。
一棵树不可能知道她刚刚连接了一棵新树，因此重要的是每棵连接到第二棵树的树都会通知第二棵树更新其高度。
这个信息可以传给第二棵树的根，以后用来判断（如前所述）哪棵树是最小的。请记住，将一棵小树连接到一棵大树而不是相反的大树会为您节省大量时间。