分享一个$O(nm)$的解法
把这些点从左往右从上到下编号序号
比如题解中的 2 2便可以变成这样
1 2
3 4
之后再根据编号建边就好了
#include <iostream>
using namespace std;
const int N = 2 * 1e6 + 100;
struct tree{
int u,v,w;
bool operator< (const tree &a) const{
return w < a.w;
}
}e[N];
int p[N];
int find(int x)
{
if(x != p[x]) p[x] = find(p[x]);
return p[x];
}
int main()
{
int m,n;
cin>>m>>n;
for(int i = 1;i <= m * n;i ++) p[i] = i;
int x1,x2,y1,y2;
while(cin>>x1>>y1>>x2>>y2)
{
int u = (x1-1) * n + y1;
int v = (x2-1) * n + y2;
int a = find(u), b = find(v);
if(a != b) p[a] = b;
}
int k = 1;
int sum = m * n;
for(int i = 1;i <= sum;i ++)
if(i <= sum - n) e[i].u = i,e[i].v = i + n,e[i].w = 1; //建立竖向边
else break;
for(int i = 1;i <= sum;i ++)
if(i % n) e[i + sum].u = i,e[i + sum].v = i + 1,e[i + sum].w = 2; //建立横向边
int ans = 0;
for(int i = 1;i <= 2 * sum;i ++) //然后便可以朴素的进行Kruskal算法
{
int a = find(e[i].u),b = find(e[i].v),w = e[i].w;
if(!w) continue;//在建边的时候有漏掉的编号,跳过就好了
if(a != b)
{
ans += w;
p[a] = b;
}
}
cout<<ans;
}