在图的连通性问题中，我们有时候需要判断两图是否连通同构，本文给出两种配合并查集的判断方法。

哈希

对每个顶点$V$，生成一个随机权值，当两个区域合并时将两个区域的所对应权值异或，若两个图所有区域的权值之和相同就可以认为是连通同构。

伪代码如下：

随机初始化每个并查集（此时是每个顶点）权值w[i]
初始化图权值和
def merge(u, v):    
    x, y = w[find(u)], w[find(v)]
    并查集合并(u, v)
    图权值和 -= (x + y)
    图权值和 += (x xor y)
    w[find(u)] = x xor y
    
for 每条边x in 边:
    并查集merge顶点merge(u, v)
    if 图1权值和 == 图2权值和
        两张图连通同构

队列

对两张图$G_1,G_2$，维护两个队列$Q_1,Q_2$，当其中一张图有加边操作时，在另一张图的队列里加入这条边，每次操作完成后判断队列内的边是否是连通的，若是，则弹出。当两个队列均为空的时候，则可认为两张图连通同构。

伪代码如下：

初始化Queue_1 Queue_2
for 每条边x in 边:
    并查集merge顶点<u,v>
    向另一张图的队列内压入x
    for 每条边y in Queue_1:
        if 连通:
            Queue_1.pop()
        else:
            break
            
    for 每条边y in Queue_2:
        if 连通:
            Queue_2.pop()
        else:
            break
            
    if Queue_1.empty() and Queue_2.empty():
        两张图连通同构