思路
分析
已有的边先加入并查集,后面的边按照kruskal做。
由于边权只有1和2,做优化不排序,先入1边(纵边)再入2边(横边)
我们更习惯$n$行$m$列,这里就以此为标准(输入时$n$,$m$换位置就行)
需要注意的是入纵边,竖直方向遍历从$[1,n - 1]$;入横边,水平方向上从$[1,m - 1]$
点$(x,y)$映射到$[1 , n m]$。
code
/*
* @Author: 爱学习的图灵机
* @Date: 2022-02-17 22:00:10
* @LastEditTime: 2022-02-17 22:00:11
* @LastEditors: 爱学习的图灵机
* Bilibili:https://space.bilibili.com/7469540
* 题目地址:https://www.acwing.com/activity/content/problem/content/1515/
* @keywords: 最小生成树
*/
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010;
int n, m, res;
int p[N * N];
int find(int x){
return x == p[x] ? x : p[x] = find(p[x]);
}
int get(int x,int y){
return (x - 1) * m + y; //一行一行放, 第x行y列, 从(1, 1)开始
}
int main()
{
cin >> n >> m; // n行 m列
for(int i = 1; i <= n * m; ++ i)p[i] = i;
int x1, y1, x2, y2;
while(~ scanf("%d%d%d%d",&x1, &y1, &x2, &y2)){
int a = find(get(x1, y1)), b = find(get(x2, y2));
// if(a != b){ //直接合并就ok
p[a] = b;
//}
}
// 纵边 必须先处理才符合kruskal按边排序
for(int i = 1; i < n; ++ i){
for(int j = 1; j <= m; ++ j){
int a = find(get(i, j)), b = find(get(i + 1, j));
if(a != b){
p[a] = b;
res += 1;
}
}
}
// 横边
for(int i = 1; i <= n; ++ i){
for(int j = 1; j < m; ++ j){
int a = find(get(i, j)), b = find(get(i, j + 1));
if(a != b){
p[a] = b;
res += 2;
}
}
}
cout << res << endl;
return 0;
}