seo关键词优化推荐_上海网络维护找哪家好_网络推广公司哪里好_网站排名优化培训课程

题目

并查集模板

算法核心就是
1、查找

int find(int x) {if (d[x] == x)return x;elsereturn d[x] = find(d[x]);//注意这儿是一个赋值，不是判等//最终返回的也是一个d[x]的值
}

2、合并

void unity(int a, int b) {d[find(a)] = find(b);//注意这是先找到a,b的根，再将b的根赋给a的根
}

3、判断是否是根节点
if（d[i]==i） ans++;

4、模板

还模板！
什么都想走捷径！！
这道题就是标准的并查集题目，这道题的代码就是模板！！！！

分析

并查集（Union-Find）是一种数据结构，专门解决这种“分组”，最后问有多少个组的问题。

代码

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <math.h>
#include <queue>#include <cctype>
using namespace std;
int n, m, k;
int d[1000010], q[1000010];
long long ans;
//找根
int find(int x) {if (d[x] == x)return x;elsereturn d[x] = find(d[x]);//注意这儿是一个赋值，不是判等//最终返回的也是一个d[x]的值
}//合并
void unity(int a, int b) {d[find(a)] = find(b);//注意这是先找到a,b的根，再将b的根赋给a的根
}int main() {cin >> m >> n >> k;for (int i = 1; i <= n * m; i++)//先初始化，每个节点的根是本身d[i] = i;for (int i = 0; i < k; i++) {int a, b;cin >> a >> b;unity(a, b);//合并2个节点的根}//找根for (int i = 1; i <= m * n; i++) {//定义q来标记根节点，避免重复添加if (q[find(i) ] == 0) {q[find(i)]++;ans++;}}
//找根的代码可以换成
//	for(int i=1;i<=m*n;i++){
//		if(d[i]==i) ans++;
//	}cout << ans << endl;return 0;
}