AcWing 1144. 连接格点 - python实现
原题链接
简单
作者:
roon2300
,
2020-07-13 21:55:32
,
所有人可见
,
阅读 620
m, n = map(int, input().split())
# 坐标编号
idx = [[0] * (n + 1) for _ in range(m + 1)]
tt = 0
for i in range(m + 1):
for j in range(n + 1):
idx[i][j] = tt
tt += 1
cnt, ans = 0, 0
fa = list(range((m + 1) * (n + 1) + 1))
def father(x):
if fa[x] == x: return x
fa[x] = father(fa[x])
return fa[x]
# 读取必需边
import sys
for line in sys.stdin:
x1, y1, x2, y2 = map(int, line.split())
fx1, fx2 = father(idx[x1][y1]), father(idx[x2][y2])
if fx1 != fx2:
fa[fx1] = fx2
cnt += 1
# 竖向连接边
for i in range(1, m):
for j in range(1, n + 1):
fx1, fx2 = father(idx[i][j]), father(idx[i + 1][j])
if fx1 == fx2: continue
fa[fx1] = fx2
ans += 1
cnt += 1
# 横向连接边
for i in range(1, m + 1):
for j in range(1, n):
fx1, fx2 = father(idx[i][j]), father(idx[i][j + 1])
if fx1 == fx2: continue
fa[fx1] = fx2
ans += 2
cnt += 1
print(ans)