G-JZTXT

#include<bits/stdc++.h>
using namespace std;
int n,m,cnt,fa[10000005],t,s1,a[1005][1005];
bool vis[10005][10005];
const short dx[]={1,0};
const short dy[]={0,1};
struct node{
	int u,v,w;
}e[10000005];
bool cmp(node a,node b){
	return a.w<b.w;
}
void init(){
	for(int i=1;i<=m*n;i++){
		fa[i]=i;
	}
}
bool merge(int a,int b){
	int q=fa[a];
	int p=fa[b];
	if(p==q)return 0;
	for(int i=1;i<=m*n;i++){
		if(fa[i]==p){
			fa[i]=q;
		}
	}
	return 1;
}
int kruskal(){
	int t1=m*n-s1;
	int ans=0;
	stable_sort(e,e+cnt,cmp);
	for(int i=0;i<cnt;i++){
		if(merge(e[i].u,e[i].v)){
			ans+=e[i].w;
			t1--;
			if(t1==1) return ans;
		}
	}
	return 0;
}
int main(){
	cin>>m>>n;
	int x,y,xx,yy;
	for(int i=1;i<=m;i++){
		for(int j=1;j<=n;j++){
			t++;
			a[i][j]=t;
		}
	}
	while(cin>>x>>y>>xx>>yy){
		merge(a[x][y],a[xx][yy]);
		vis[a[x][y]][a[xx][yy]]=true;
		s1++;
	}
	for(int i=1;i<=m;i++){
		for(int j=1;j<=n;j++){
			for(int h=0;h<2;h++){
				int nx=i+dx[h];
				int ny=j+dy[h];
				if(nx<1||ny<1||nx>m||ny>n||vis[a[i][j]][a[nx][ny]])continue;
				e[cnt].u=a[i][j];
				e[cnt].v=a[nx][ny];
				if(h==0)e[cnt].w=1;
				else e[cnt].w=2;
				cnt++;
			}
		}
	}
	init();
	int s=kruskal();
	cout<<s<<endl;
	return 0;
}