1 条题解

  • 0
    @ 2024-2-19 14:45:18
    #include<bits/stdc++.h>
    using namespace std;
    int n,m;
    int f[10000050];
    int ans;
    //并查集 
    int find(int x){
    	if(f[x]==x)return x;
    	return f[x]=find(f[x]);
    	
    }
    int merge(int x,int y){
    	int fx=find(x);
    	int fy=find(y);
    	
    	if(fx!=fy){
    		f[fx]=fy;
    		return 1;
    	}
    	return 0;
    }
    int main(){
    cin>>n>>m;
    for(int i=1;i<=n*m;i++){//初始化 
    	f[i]=i;
    	
    } 
    int x1,x2,y1,y2;
    while(cin>>x1>>y1>>x2>>y2){
    	int u=(x1-1)*m+y1,v=(x2-1)*m+y2;
    	merge(u,v);}
    	for(int i=1;i<=m;i++){//先连接纵向 
    		for(int j=1;j<n;j++){
    			int u=(j-1)*m+i,v=j*m+i;//点(i,j),(i,j+1) 
    			if(merge(u,v))ans++;
    		}
    	}
    	for(int i=1;i<=n;i++){//后连接纵向 
    		for(int j=1;j<m;j++){
    			int u=(i-1)*m+j,v=(i-1)*m+j+1;//点(i,j),(i+1,j) 
    			if(merge(u,v))ans+=2;
    		}
    	}
    	cout<<ans<<endl;
    	return 0;
    }
    
    • 1

    信息

    ID
    589
    时间
    1000ms
    内存
    128MiB
    难度
    8
    标签
    (无)
    递交数
    50
    已通过
    7
    上传者