About
Ŝalenzo Website (3)
Subscribe
Subscribe to a syndicated feed of my weblog,
brought to you by the wonders of RSS.
Links
These are a few of my favourite links.
并并集：一种很新的数据结构（迫真）
众所周知，并查集有合并和查询两种操作，故名并查集。并并集出于并查集而烂于并查集，不支持查询，让一切数据无据可查！（不是
经典并并集可用简单的C实现。例如，LeetCode第547题省份数量可用下列代码实现。
```c void join(void *x, void y) { return x != y ? *join(x, x) = join(y, y) : x != *x ? *x = join(x, *x) : x; }
int findCircleNum(int* g, int n, int unused) { // 初始化。 void *u[n]; for (int i = 0; i < n; i++) u[i] = u+i; // 求并。 for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (g[i][j] == 1) join(u+i, u+j); } } // 计数。 int ans = 0; for (int i = 0; i < n; i++) if (u[i] == u+i) ans++; return ans; } ```
注意C语法规则允许?:三目运算符之间存在优先级更低的运算，?和:具有类似括号的作用。join函数会带来大量警告，但无视之。这与传统并查集并没有很大的区别，只是换索引为指针，并一并实现find和union操作。这样，join函数不必获得整个数组的访问权限。
因为find和union统一起来了，所以能使合并时产生的结构比传统的先查找后指向的实现少一层。两种这样的写法如下：
```c void join(void *x, void y) { return x != *x ? *x = join(x, y) : y != y ? *y = join(x, *y) : (y = x); }
void join(void *x, void y) { return x != x ? *x = join(x, y) : (y = y != *y ? join(x, *y) : x); } ```
更易于理解的版本：
c
void **join(void **x, void **y) {
if (x != *x) {
*x = join(*x, y);
} else if (y != *y) {
*y = join(x, *y);
} else {
*y = x;
}
return *y;
}
如果将递归栈展平到局部变量，就会类似于下列使用STL的C++代码。
cpp
void **join(void **x, void **y) {
vector<void **> a;
for (; x != *x; x = (void **) *x) a.push_back(x);
for (; y != *y; y = (void **) *y) a.push_back(y);
a.push_back(y);
for (auto z : a) *z = x;
return x;
}
这实际上是我在阅读并查集原理后的最初实现，只是用了Python，并且使用了Solution方便对象上的属性代替指针。
python
class Solution:
def findCircleNum(self, isConnected: List[List[int]]) -> int:
self.a = [Solution() for _ in range(len(isConnected))]
for i in range(len(isConnected)):
self.a[i].next = self.a[i]
for i in range(len(isConnected)):
for j in range(i + 1, len(isConnected)):
if isConnected[i][j]:
self.connect(self.a[i], self.a[j])
for i in range(len(isConnected)):
self.connect(self.a[i], self.a[i])
return len({x.next for x in self.a})
def connect(self, i, j):
a = set()
while i.next != i:
a.add(i)
i = i.next
while j.next != j:
a.add(j)
j = j.next
a.add(j)
for k in a:
k.next = i
以上并并集的实现都没有在合并时多加考虑，而是任意合并，最坏时间复杂度可达
。
更新：并并集也很容易改为用NULL初始化，即可利用memset高速化。注意此时必须判断x与y不属于同一集合才实行合并。
c
void **join(void **x, void **y) {
return *x ? *x = join(*x, y) : *y ? join(y, x) : x != y ? *x = y : x;
}