(算法)两个人是否为队友
算法 是否 两个
2023-09-14 09:00:36 时间
题目:
百度全体员工玩分组游戏,前面五分钟大家分头找队友,并将每个人找到的队友信息汇报给主持人,如果A和B是队友,B和C是队友,那么A和C也是队友;接着主持人不断地随机抽取两个人,希望判断二者是否为队友。请设计一个计算机程序辅助主持人判断两个人是否为队友,说明程序的关键算法,不需要代码实现。
例如:
<小明,小王>,<小军,小王>,<小丽,小李>是队友,那么小军和小明是队友,小军和小丽不是队友。
思路:
典型的并查集(Union-Find)应用。
并查集:我们可以把每个连通分量看成一个集合,该集合包含了连通分量的所有点。而具体的连通方式无关紧要,好比集合中的元素没有先后顺序之分,只有“属于”与“不属于”的区别。图的所有连通分量可以用若干个不相交集合来表示。而并查集的精妙之处在于用树来表示集合。
假设所有员工编号为1~n,那么一开始每个员工都属于自己的集合(假设为数组parents),采用的树结构则是每个员工结点的父结初始化为自己,即parents[i]=i;如果<i,j>为队友,那么将j的父结点设置为i,即parents[j]=parents[i],这样遍历所有的队友组合,就可以得到多棵树状的结构(每个集合为一棵树,见下图左);既然每个集合的元素都是队友,那么我们只需要将他们归为一类即可,因此需要将树进行压缩,压缩的过程就是不断的往上搜索(见下图右)。
如何判断两个员工是否为队友呢?只要看他们是否属于同一个集合,即同一个父结点。
并查集的应用:求最小生成树的Kruskal算法。
代码:
#include <iostream> #include <vector> using namespace std; typedef pair<int,int> Pair; void findParent(const vector<Pair> &friends,vector<int> &parents){ int sz=friends.size(); for(int i=0;i<sz;i++){ Pair cp=friends[i]; if(cp.first!=cp.second){ parents[cp.second]=parents[cp.first]; } } } int getParent(const vector<int> &parents,int i){ while(i!=parents[i]) i=parents[i]; return i; } bool isFriend(const vector<int> &parents,Pair friends){ int f1=friends.first; int f2=friends.second; return getParent(parents,f1)==getParent(parents,f2); } int main() { vector<Pair> friends; Pair p[5]={Pair(1,3),Pair(2,5),Pair(3,6),Pair(6,7),Pair(1,4)}; for(int i=0;i<5;i++){ friends.push_back(p[i]); } int num=7; vector<int> parents(num+1); for(int i=0;i<=num;i++) parents[i]=i; findParent(friends,parents); Pair f(1,7); cout<<isFriend(parents,f)<<endl; return 0; }
相关文章
- C++实现算法常用的STL---整理
- Java实现 蓝桥杯VIP 算法提高 Quadratic Equation
- Java实现 蓝桥杯VIP 算法提高 班级排名
- Java实现 蓝桥杯VIP 算法训练 友好数
- Java实现蓝桥杯算法提高P0102
- (算法)是否为二叉查找树的后序遍历数组
- 数据结构与算法-7 Redis 中的数据类型 [MD]
- 数据结构和算法-面试题
- face alignment---各种算法框架
- 重新整理数据结构与算法——稀疏数组[二]
- 【YOLOv8/YOLOv7/YOLOv5/YOLOv4/Faster-rcnn系列算法改进NO.60】损失函数改进为wiou
- Atitit Seed-Filling种子填充算法attilax总结
- DataScience:数据预处理/特征工程之线性变换—四种特征缩放Scaling算法简介、标准化standardization、归一化Normalization的概述与区别
- CV之IC:基于Keras框架利用mini_XCEPTION算法实现训练性别分类hdf5模型导出并保存到指定文件夹下代码实现
- ML之CatBoost:金融风控之通过数据预处理(中位数填充/校验同分布/文本型日期拆解/平均数编码-标签编码)利用CatBoost算法+模型可解释性(Shap/LIME)预测用户的车险是否为欺诈行为
- ML之xgboost:利用xgboost算法(sklearn+3Split)训练mushroom蘑菇数据集(22+1,6513+1611)来预测蘑菇是否毒性(二分类预测)
- ML之xgboost:利用xgboost算法(自带方式)训练mushroom蘑菇数据集(22+1,6513+1611)来预测蘑菇是否毒性(二分类预测)
- ML之RF&XGBoost:基于RF/XGBoost(均+5f-CrVa)算法对Titanic(泰坦尼克号)数据集进行二分类预测(乘客是否生还)
- AutoML之flaml:基于OpenML数据集利用flaml框架自定义RGF算法/自定义优化指标来自动寻优实现预测航班是否延误二分类任务案例之详细攻略
- ML之回归预测:机器学习中的各种Regression回归算法、关键步骤配图
- ML之xgboost:利用xgboost算法(sklearn+3Split+调参曲线)训练mushroom蘑菇数据集(22+1,6513+1611)来预测蘑菇是否毒性(二分类预测)
- 【路径优化】基于帝企鹅算法求解TSP问题(Matlab代码实现)
- m基于多相位功率倒置的GPS抗干扰算法matlab仿真
- 智能优化算法:教与学优化算法-附代码
- 判断一个坐标点是否在不规则多边形内部的算法
- floyd算法入门
- 《算法入门经典大赛——培训指南》第二章考试