编程学习笔记14--并查集的问题
扫描二维码
随时随地手机看文章
并查集
Union-Find Set或Disjoint Set(不相交集合),将编号分别为1…N的N个对象划分为不相交集合,在每个集合中,选择其中某个元素代表所在集合。
常见的操作
合并两个集合;将一元素并入另一集体;判断两个元素是否属于同一个集合;每个集合用一棵“有根树”表示.
实现方法
每个集合用一棵“有根树”表示,定义数组 set[1..n],set[i] = i , 则i表示本集合,并是集合对应树的根,set[i] = j, j!=i, 则 j 是 i 的父节点.
树形结构,只需记录每个结点的父结点即可,每棵树表示一个集合,树的根作为集合的“代表元”。
对于查找操作,实际上沿着父指针,向上找到根即可
对于合并操作:只要把一个集合的根节点和另一个集合连接就可以了。
判断是否属于同一个集合的方法:由此用某个元素所在树的根结点表示该元素所在的集合,判断两个元素时候属于同一个集合的时候,只需要判断他们所在树的根结点是否一样
即可也就是说,当我们合并两个集合的时候,只需要在两个根结点之间连边即可
HDOJ 1232 Problem Description
某省调查城镇交通状况,得到现有城镇道路统计表,表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通(但不一定有直接的道路相连,只要互相间接通过道路可达即可)。问最少还需要建设多少条道路?
测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数,分别是城镇数目N ( < 1000 )和道路数目M;随后的M行对应M条道路,每行给出一对正整数,分别是该条道路直接连通的两个城镇的编号。为简单起见,城镇从1到N编号。
注意:两个城市之间可以有多条道路相通,也就是说 3 3 1 2 1 2 2 1 这种输入也是合法的
当N为0时,输入结束,该用例不被处理。
对每个测试用例,在1行里输出最少还需要建设的道路数目。
地图上若干城镇都可以看作点,已知哪些对城镇之间是有道路直接相连的。最后要解决的是整幅图的连通性问题,即求整幅图一共有几个连通分支,也就是被分成了几个互相独立的块。
畅通工程这题,问还需要修几条路,实质就是求有几个连通分支。如果是1个连通分支,说明整幅图上的点都连起来了,不用再修路了;如果是2个连通分支,则只要再修1条路,从两个分支中各选一个点,把它们连起来,那么所有的点都是连起来的了;如果是n个连通分支,则只要再修n-1条路。
#include#define M 1000 int F[M];//并查集的根节点保存的数组 void Init(int *F)//初始化 { int i=0; for(i=0;i<M;i++) F[i]=i; } int find(int x)//查找元素所在的集合 { while(F[x]!=x) { x=F[x]; } return x; } void Union(int u, int v) { int s1 = find(u), s2 = find(v); if (s1 != s2) F[s1] = s2; } int main() { int n,m;//城镇数目n和道路数目m int m_a,m_b;//m行测试数据的对应的两个数据,表示城镇ma和mb之间联通 int i,count=0; freopen("input.txt","r",stdin); while(scanf("%d %d",&n,&m)) { count=0; if(n==0) break; Init(F); while(m--) { scanf("%d %d",&m_a,&m_b);//把两个节点结合起来 Union(m_a,m_b); } for(i=1;i<=n;i++) { if(F[i]==i) { count++; } } printf("%dn",count-1);//因为如果全部连接起来的话,根节点的还是会有i还是满足i=F[i]的。 } }
优化——路径压缩
思想:每次查找的时候,如果路径较长,则修改信息,以便下次查找的时候速度更快。
第一步,找到根结点
第二步,修改查找路径上的所有节点,将它们都指向根结点
带路径压缩的查找算法
int find(int x) { int k, j, r; r = x; while(r != parent[r]) //查找跟节点 r = parent[r]; //找到跟节点,用r记录下 k = x; while(k != r) //非递归路径压缩操作 { j = parent[k]; //用j暂存parent[k]的父节点 parent[k] = r; //parent[x]指向跟节点 k = j; //k移到父节点 } return r; //返回根节点的值 }
int find(int x) //查找x元素所在的集合,回溯时压缩路径 { if (x != parent[x]) { parent[x] = find(parent[x]); //回溯时的压缩路径 } //从x结点搜索到祖先结点所经过的结点都指向该祖先结点 return parent[x]; } //采用递归的方式压缩路径, 但是,递归压缩路径可能会造成溢出栈