当前位置:网站首页>并查集实践
并查集实践
2022-07-05 22:50:00 【BugMaker-shen】
是不是亲戚问题
我们使用merge的优化,就不使用find的优化了
#include <iostream>
#include <vector>
using namespace std;
int SIZE = 0;
int* parent = nullptr; // 记录每个节点的父节点
int* height = nullptr; // 记录根节点的层高
// 返回x所在树的根节点的编号
int find_root(int x) {
if (x <= 0 || x >= SIZE) {
return -1;
}
while (x != parent[x]) {
x = parent[x];
}
return x;
}
// 合并x和y所在的集合
void merge(int x, int y) {
x = find_root(x);
y = find_root(y);
if (x != y) {
// 这里x和y都是根节点,谁矮谁作为孩子节点
if (height[x] > height[y]) {
parent[y] = x;
}
else {
if (height[x] == height[y]) {
// y作为合并以后树的根,根节点高度要+1
height[y]++;
}
parent[x] = y;
}
}
}
int main() {
int m = 0;
int p = 0;
int n = 0;
cin >> n >> m >> p;
SIZE = n + 1;
parent = new int[SIZE];
height = new int[SIZE];
for (int i = 0; i < SIZE; i++) {
height[i] = 1;
parent[i] = i; // 一开始,每个节点的父节点就是自己
}
int p1, p2; // 两个人
for (int i = 0; i < m; i++) {
cin >> p1 >> p2;
merge(p1, p2);
}
vector<pair<int, int>> query;
for (int i = 0; i < p; i++) {
cin >> p1 >> p2;
query.push_back(pair<int, int>(p1, p2));
}
for (auto q : query) {
cout << (find_root(q.first) == find_root(q.second) ? "YES" : "NO") << endl;
}
delete[] parent;
delete[] height;
parent = nullptr;
height = nullptr;
return 0;
}
/* 6 5 3 1 2 1 5 3 4 5 2 1 3 1 4 2 3 5 6 */
躲避拥堵的最佳路线
3 3 1 3 # 3个区、3条边、从1区到3区
1 2 2 # 从1区到2区的拥挤度为2
2 3 1
1 3 3
题目说规划一条路径,使得经过道路的拥挤度的最大值最小。该测试用例输出2,是说我们从1区到3区,可以走1->2->3,此时拥挤度的最大值为2;也可以走1->3,此时拥挤度的最大值为3;故该测试用例输出2
我们使用kruskal算法,先从拥挤度小的边开始选取,直到连通s区和t区,这样最后一条选取的边一定是已选道路拥挤度最大的,未选道路拥挤度最小的,这样就能做到在连通的基础上所选取的最大值最小
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int* parent = nullptr;
struct Edge {
Edge(int start, int end, int w)
: start_(start)
, end_(end)
, w_(w)
{
}
int start_;
int end_;
int w_;
};
// 找编号为x的节点的根节点
int find(int x) {
if (x == parent[x]) {
return x;
}
else {
// find优化,查找根节点的过程中,把遍历过的节点的父节点都改成根节点
parent[x] = find(parent[x]);
return parent[x];
}
}
int main(){
int n, num_edge, s, t;
cin >> n >> num_edge >> s >> t;
parent = new int[n + 1](); // n个区,为了让编号和下标对应,多开辟一个
vector<Edge> edges;
int start, end, w;
for (int i = 0; i < num_edge; i++) {
cin >> start >> end >> w;
edges.emplace_back(start, end, w);
// 初始化parent数组
parent[start] = start;
parent[end] = end;
}
// 边进行升序排列
sort(edges.begin(), edges.end(),
[](const Edge& e1, const Edge& e2) ->bool{
return e1.w_ < e2.w_;
});
for (int i = 0; i < num_edge; i++) {
int root1 = find(edges[i].start_);
int root2 = find(edges[i].end_);
if (root1 != root2) {
// 根节点不同,可以连接
parent[root1] = root2;
if (find(s) == find(t)) {
// 选择了新的边,才会判断是否连通了s区和t区;本轮循环没有选择新的边,则没有必要判断是否连通s区和t区
cout << edges[i].w_ << endl;
}
}
}
delete[] parent;
return 0;
}
/* 3 3 1 3 1 2 2 2 3 1 1 3 3 */
边栏推荐
- Metasploit(msf)利用ms17_010(永恒之蓝)出现Encoding::UndefinedConversionError问题
- Hcip day 11 (BGP agreement)
- fibonacci search
- Global and Chinese market of water treatment technology 2022-2028: Research Report on technology, participants, trends, market size and share
- Arduino measures AC current
- Registration and skills of hoisting machinery command examination in 2022
- APK加固技术的演变,APK加固技术和不足之处
- Global and Chinese market of diesel fire pump 2022-2028: Research Report on technology, participants, trends, market size and share
- [untitled]
- Marginal probability and conditional probability
猜你喜欢
[untitled]
[untitled]
[speech processing] speech signal denoising based on Matlab GUI Hanning window fir notch filter [including Matlab source code 1711]
Starting from 1.5, build a micro Service Framework -- log tracking traceid
d3dx9_ What if 29.dll is missing? System missing d3dx9_ Solution of 29.dll file
How can easycvr cluster deployment solve the massive video access and concurrency requirements in the project?
Arduino 测量交流电流
TCC of distributed solutions
Double pointeur de liste liée (pointeur rapide et lent, pointeur séquentiel, pointeur de tête et de queue)
查看网页最后修改时间方法以及原理简介
随机推荐
Nacos 的安装与服务的注册
派对的最大快乐值
Codeforces Global Round 19
Nacos installation and service registration
一文搞定JVM常见工具和优化策略
Global and Chinese markets for reciprocating seal compressors 2022-2028: Research Report on technology, participants, trends, market size and share
My experience and summary of the new Zhongtai model
[screen recording] how to record in the OBS area
Paddle Serving v0.9.0 重磅发布多机多卡分布式推理框架
513. Find the value in the lower left corner of the tree
Arduino measures AC current
Negative sampling
SPSS analysis of employment problems of college graduates
Function default parameters, function placeholder parameters, function overloading and precautions
谷歌地图案例
记录几个常见问题(202207)
链表之双指针(快慢指针,先后指针,首尾指针)
Unity Max and min constraint adjustment
分布式解决方案选型
从 1.5 开始搭建一个微服务框架——日志追踪 traceId