最小生成树

主要考察格点的建边和连边顺序

1. 首先输入已连边，放入克鲁斯卡尔的并查集中

2. 之后先对竖的边进行连接，再对横的边进行连接，求最小生成树

注意，这里为了使得节点的唯一性，将二维坐标进行一维编码，具体就是：$$将(x,y)变成→x*n+y$$保证坐标点的唯一性

python版本

#连接格点
#1143. 联络员
class UFS():
    def __init__(self,n):
        self.father = {}
        self.size = {}
        for i in range(1,n+1):
            self.size[i] = 1
            self.father[i] = i

    def findRoot(self,node):
        father = self.father[node]
        if father != node:
            father = self.findRoot(father)
        self.father[node] = father
        return father

    def union(self,node_a,node_b):
        root_a = self.findRoot(node_a)
        root_b = self.findRoot(node_b)
        if root_a != root_b:
            if self.size[root_a] > self.size[root_b]:
                self.father[root_b] = root_a
                self.size[root_a] += self.size[root_b]
            else:
                self.father[root_a] = root_b
                self.size[root_b] += self.size[root_a]
            return True

        return False



m,n = map(int,input().split())

data = []  #已有边


while True:
    try:
        a,b,c,d = map(int,input().split())
        data.append(((a - 1)*n + b,(c - 1)*n + d))  #已有边
    except:
        break


ufs = UFS(n*m)
res = 0

for var in data:
    ufs.union(var[0],var[1])

for x in range(m):
    for y in range(1,n+1):
        if x - 1 >= 1:
            if ufs.union(x*n + y,(x - 1)*n + y):
                res += 1
        if x + 1 < m:
            if ufs.union(x*n + y,(x + 1)*n + y):
                res += 1

for x in range(m):
    for y in range(1,n+1):
        if y - 1 >= 2:
            if ufs.union(x*n + y,x*n + y - 1):
                res += 2
        if y + 1 <=  n:
            if ufs.union(x*n + y,x*n + y + 1):
                res += 2

print(res)