1 条题解
-
0
#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
- 上传者