本文转载自:http://www.javaxxz.com/thread-359245-1-1.html
并查集这玩意上课老师没讲,听上去就很高大上,一看到题目说要用并查集,ψ(。。)什么!?并查集?什么玩意?算了算了,放弃这道题刷别的吧。今天研究了下并查集,发现还是挺简单的,博客上做个整理,以后忘了上来瞅瞅_(¦3」∠)_
并查集
并查集主要是用来检测两个点是否连通的,主要有两个功能,一个是find一个是join。至于什么时候用并查集,我想大概是你觉得需要判断这两个点是否连通吧,例如,几个个城市之间有几条几条路,判断其中两个城市是否连通。
①并查集的初始化
并查集一般是用一个一维数组来存储的,其中pre[i]=i表示自己和自己是连通的,也就是说还没有往点之间添加路径。
②并查集join
join主要是用来往存放并查集的一维数组中添加路径的,先判断两个点之间是否连通,如果连通就不用添加路径了,如果不连通那么将两个点的根节点连在一起。
void join(int x,int y){ int i,j; i = find(x); //寻找x的根节点 j = find(y); //寻找y的根节点 if(i!=j) //如果两个根节点不同,即不连通,将根节点连在一起 pre[i] = j; //即i链接j }
③并查集find
find主要有两个部分,一个是寻找根节点,一个是将路径压缩。
int find(int x){ int i = x; while(pre[i]!=i) //查找根节点 i = pre[i]; //路径压缩 int j = x; int k; while(j!=i) { k = pre[j]; pre[j] = i; j = k; } return i;}
下面有两道例题来详细讲解一下并查集的用法
蓝桥杯 历届试题 风险度量
X星系的的防卫体系包含 n 个空间站。这 n 个空间站间有 m 条通信链路,构成通信网。
两个空间站间可能直接通信,也可能通过其它空间站中转。
对于两个站点x和y (x != y), 如果能找到一个站点z,使得:
当z被破坏后,x和y无法通信,则称z为关于x,y的关键站点。
显然,对于给定的两个站点,关于它们的关键点的个数越多,通信风险越大。
你的任务是:已知网络结构,求两站点之间的通信风险度,即:它们之间的关键点的个数。
输入数据第一行包含2个整数n(2 <= n <= 1000), m(0 <= m <= 2000),分别代表站点数,链路数。
空间站的编号从1到n。通信链路用其两端的站点编号表示。
接下来m行,每行两个整数 u,v (1 <= u, v <= n; u != v)代表一条链路。
最后1行,两个数u,v,代表被询问通信风险度的两个站点。
输出:一个整数,如果询问的两点不连通则输出-1.
例如:
用户输入:
7 6
1 3
2 3
3 4
3 5
4 5
5 6
1 6
则程序应该输出:
2
#include<iostream>using namespace std;int pre[1001];int u[2001],v[2001];int find(int x){ int i = x; while(pre[i]!=i) //查找根节点 i = pre[i]; //路径压缩 int j = x; int k; while(j!=i) { k = pre[j]; pre[j] = i; j = k; } return i;}void join(int x,int y){ int i,j; i = find(x); j = find(y); if(i!=j) pre[i] = j;}int main(){ int n,m; cin>>n>>m; int i,x,y; for(i=0;i<n;i++) pre[i] = i; for(i=0;i<m;i++) { cin>>x>>y; u[i] = x; v[i] = y; join(x,y); } cin>>x>>y; if(find(x)!=find(y)) //如果不连通就输出-1 cout<<"-1"<<endl; else //如果连通,寻找有几个关键站点 { int res = 0; for(i=0;i<n;i++) //因为数据很小,所以暴力枚举,从第一个站点开始判断是否是关键站点 { if(i==x||i==y) //如果i是x和y这两个需要判断是否连通的站点的其中一个就跳过 continue; for(int k=0;k<n;k++) //初始化pre数组 pre[k] = k; for(int j=0;j<m;j++) //按照输入顺序jion { if(u[j]==i||v[j]==i) //如果是i这个站点,就不在pre里面加链接这个站点的路径 continue; join(u[j],v[j]); } if(find(x)!=find(y)) //如果x和y不连通了,说明站点i是关键站点 res++; } cout<<res<<endl; } return 0;}
2005年浙江大学计算机复试 通畅工程 NYOJ608
畅通工程
注意:两个城市之间可以有多条道路相通,也就是说
3 3
1 2
1 2
2 1
这种输入也是合法的
当N为0时,输入结束,该用例不被处理。
4 21 34 33 31 21 32 35 21 23 5999 00
102998
这个题好烦,WA了好多次最后发现是一个小小小错误,还有说我超时,把cin全部换成scanf什么的了。还有一种写法比这个感觉稍微麻烦一点点,可以了解一下。
方法二:要将n个站点相连通,也就是要将每个连通路径的根节点相连通,求出根节点的数量num,最终还需要修建的路径数就为num-1。
#include<iostream>#include<stdio.h>using namespace std;int pre[1005];int find(int x){ int i = x; while(pre[i]!=i) i = pre[i]; return i;}int main(){ int n,m; int i,a,b,total,fa,fb; while(scanf("%d",&n) && n!=0) { scanf("%d",&m); total = n-1; //n个站点全部连通最少需要n-1条路径 for(i=1;i<=n;i++) pre[i] = i; for(i=1;i<=m;i++) { scanf("%d%d",&a,&b); fa = find(a); fb = find(b); if(fa!=fb) pre[fa] = fb; } for(i=1;i<=n;i++) { if(pre[i]!=i) //也就是有相连的路径 total --; } printf("%d\n",total); } return 0;}
相关推荐
更新:更新日期分类算法2021/02/14数据结构树状数组2021/02/15数据结构并查集与种类并查集2021/02/16数据结构线段树2021/02/17其他离散化2021/02/17数据结构st表2021/02/19数据结构分块2021/03/01分治三分搜寻2021/...
数据结构与算法笔记+LeetCode经典例题分析。...其中包括八大排序算法、动态规划背包问题、深度优先搜索、广度优先搜索、队列、优先队列、栈、并查集、树、二叉树、二叉搜索树、AVL平衡二叉树等等。
简介力扣常见检查的知识点大概有一些种,包括:二分,滑动窗口,双指针,单调栈(单调栈),链表,二叉树,串处理,dfs +回溯,并查集,动态规划,贪心,位运算,数论(质数,约数,欧拉函数,欧几里得算法,中国...
算法思想:将高维空间中的元素视为点并赋以坐标值,坐标值为正整数。通过一族哈希函数将空间所有点映射到n个哈希表中,n=||,即每个哈希函数f对应一个哈希表,每个哈希表都存放着空间所有的点。对于给定的查询子q,...
主要处理边缘情况时间/空间复杂度分析专题排序链表题LRU 二分位运算栈和含量堆二叉树贪心并查集图动态规划单调栈滑动窗口和双指针完美洗牌问题斐波那契问题和扩展蓄水池算法计算表达式首要树Manacher算法KMP算法...
leetcode双人赛 1 前言 ...并查集 2.5 图论 最短路 最小生成树 2.6 数论 辗转相除法 素数 快速幂 3 中级算法 3.1 二分搜索 最大化最小值 01分数规划 第k大值 最小化第k大值 其他二分搜索 3.2 常用技巧
个算法分别是:二分法,递归,回溯法,排序,双指针,滑动窗口,并查集 5 个算法思想分别是:分治,贪心,深度优先遍历,广度优先遍历,动态规划 (二)题目分类 Array List Math Stack String Tree (三)题目代码 ...
并查集 堆 哈希表 DFS BFS 快速幂 背包问题 区间DP 区间问题 绝对值不等式 DP课 寒假每日一题 基础班 提高班 POJ 大二 2019 新生赛 蓝桥杯模拟 蓝桥杯学习 bfs 大数 dfs/抽象dfs 逻辑 测试 栈/递归 清华oj入门
leetcode双人赛 1 前言 ...并查集 2.5 图论 最短路 最小生成树 2.6 数论 辗转相除法 素数 快速幂 3 中级算法 3.1 二分搜索 最大化最小值 01分数规划 第k大值 最小化第k大值 其他二分搜索 3.2 常用技巧
leetcode双人赛 1 前言 ...并查集 2.5 图论 最短路 最小生成树 2.6 数论 辗转相除法 素数 快速幂 3 中级算法 3.1 二分搜索 最大化最小值 01分数规划 第k大值 最小化第k大值 其他二分搜索 3.2 常用技巧
leetcode双人赛 1 前言 ...并查集 2.5 图论 最短路 最小生成树 2.6 数论 辗转相除法 素数 快速幂 3 中级算法 3.1 二分搜索 最大化最小值 01分数规划 第k大值 最小化第k大值 其他二分搜索 3.2 常用技巧
08-- 算法的#08--深入详解并查集union-find算法 09-- 算法#09--用简单的思维理解选择,插入,冒泡和希尔排序 10-- 算法#10--用简单的思维理解堆排序 算法# 用简单的思维理解归并排序和三向快速排序 12--
【数据结构】并查集.md 【数论】快速幂全解(模平方根算法).md 【数论】素数问题.md 2. 刷题 LeetCode&剑指Offer LeetCode 1-100.md 剑指 offer 汇总.md 二分 二分法小结.md 搜索旋转排序数组.md 搜索旋转排序数组 ...
排序、并查集、栈和队列、红黑树、散列表。 对题目做了一个大致分类,并对每种题型的解题思路做了总结。 :cloud: 网络 物理层、链路层、网络层、运输层、应用层。 方法、状态码、Cookie、缓存、连接管理、HTTPs、...
数组、栈、队列、链表、二分搜索树、集合、映射、优先队列、堆、线段树、Trie、并查集、AVL、红黑树、哈希表 数据处理典型案例,逐渐更新 :hot_beverage: Java 、、基本概念、面向对象、基本数据类型与运算、字符串...
知识点:并查集、包含小写字母的字符串的处理 Day32 面试题46. 把数字翻译成字符串 知识点:动态规划,一维动态规划,dp[i]代表以i结束时有效字符串的个数 36. 有效的数独 知识点:遍历一遍数组,怎么想的怎么实现就...
leetcode中国 数据结构与算法 从四月份开始正式的断断续续刷题,有过迷茫,有过崩溃,有过看不清脚下的路,有过陷...并查集:check_box_with_check: 堆:check_box_with_check: Hash表 C++ STL使用技巧 搜索与图论 DFS与
(并查集) (滑动窗口、双指针) (动态规划、数组) (动态规划、字符串) (二叉树、前序遍历、中序遍历、递归) (递归,8皇后) TODO [最小生成树问题] TODO [动态规划-钢条切割] TODO [动态规划-矩阵乘法] ...
排序、并查集、栈和队列、红黑树、散列表。 :laptop: 操作系统 进程管理、内存管理、设备管理、链接。 基本实现原理以及基本操作。 :cloud: 网络 物理层、链路层、网络层、运输层、应用层。 方法、状态码、Cookie、...
oracle学习文档 笔记 全面 深刻 详细 通俗易懂 doc word格式 清晰 第一章 Oracle入门 一、 数据库概述 数据库(Database)是按照数据结构来组织、存储和管理数据的仓库,它产生于距今五十年前。简单来说是本身可视...