#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
int n, m;
bool flag_[1005][1005]; // 每个点和右边是否相连
bool flag1[1005][1005]; // 每个点和下面是否相连
bool flag[1005];        // 第i列与第i+1列是否相连
int fa[1000 * 1000 + 5];
int findFa(int x)
{
    if (x == fa[x])
        return x;
    return fa[x] = findFa(fa[x]);
}
int p(int x, int y)
{
    return (x - 1) * m + y;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            fa[p(i, j)] = p(i, j);
    int x, y, xx, yy;
    while (cin >> x >> y >> xx >> yy)
    {
        int u = p(x, y);
        int v = p(xx, yy);
        int faU = findFa(u);
        int faV = findFa(v);
        if (faU != faV)
            fa[faU] = faV;
    }
    // kruskal
    int ans = 0;
    // 连竖线
    for (int i = 1; i <= n - 1; i++)
        for (int j = 1; j <= m; j++)
        {
            int u = p(i, j);
            int v = p(i + 1, j);
            int faU = findFa(u);
            int faV = findFa(v);
            if (faU != faV)
            {
                fa[faU] = faV;
                ans++;
            }
        }
    // 连横线
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m - 1; j++)
        {
            int u = p(i, j);
            int v = p(i, j + 1);
            int faU = findFa(u);
            int faV = findFa(v);
            if (faU != faV)
            {
                fa[faU] = faV;
                ans += 2;
            }
        }
    cout << ans << "\n";
    return 0;
}

核心思路：将坐标转化为数字做并查集

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
const int N = 1e6 + 5;
int n, m, fa[N], sum;
inline int findFa(int x) // 并查集：找父节点
{
	if (fa[x] == x)
		return x;
	return fa[x] = findFa(fa[x]); // 记得加记忆化
}
bool unite(int x, int y) // 检查两个点是否需要联通 如果需要则做合并
{
	int xx = findFa(x), yy = findFa(y);
	if (xx == yy)
		return false;
	fa[xx] = yy;
	return true;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n * m; i++)
		fa[i] = i; // 初始化并查集
	int x1, y1, x2, y2;
	while (cin >> x1 >> y1 >> x2 >> y2 && x1 && x2 && y1 && y2)
		unite((x1 - 1) * m + y1, (x2 - 1) * m + y2); // 将坐标转换为数字
	for (int i = 1; i < n; i++)						 // 从第i行枚举到第n-1行
		for (int j = 1; j <= m; j++)				 // 枚举每一列
			if (unite((i - 1) * m + j, i * m + j))	 // 如果上下两个点没有联通 连通并记录
				sum++;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j < m; j++)
			if (unite((i - 1) * m + j, (i - 1) * m + j + 1)) // 同理 枚举左右两个点
				sum += 2;
	cout << sum << endl;
}