并并集：一种很新的数据结构（迫真）

众所周知，并查集有合并和查询两种操作，故名并查集。并并集出于并查集而烂于并查集，不支持查询，让一切数据无据可查！（不是

经典并并集可用简单的C实现。例如，LeetCode第547题省份数量可用下列代码实现。

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统一起来了，所以能使合并时产生的结构比传统的先查找后指向的实现少一层。两种这样的写法如下：

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);
}

更易于理解的版本：

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++代码。

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方便对象上的属性代替指针。

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

以上并并集的实现都没有在合并时多加考虑，而是任意合并，最坏时间复杂度可达O(n)。

更新：并并集也很容易改为用NULL初始化，即可利用memset高速化。注意此时必须判断x与y不属于同一集合才实行合并。

void **join(void **x, void **y) {
	return *x ? *x = join(*x, y) : *y ? join(y, x) : x != y ? *x = y : x;
}