上篇文章 Union-Find 并查集算法详解 很多读者对于 Union-Find 算法的应用表示很感兴趣，这篇文章就拿几道 LeetCode 题目来讲讲这个算法的巧妙用法。
图论中知名度比较高的算法应该就是 Dijkstra 最短路径算法，环检测和拓扑排序，二分图判定算法 以及今天要讲的最小生成树（Minimum Spanning Tree）算法了。
记得我之前在讲 图论算法基础 时说图论相关的算法不会经常考，但最近被打脸了，因为一些读者和我反馈近期求职面试涉及很多图论相关的算法，可能是因为环境不好所以算法这块更卷了吧。
今天讲讲 Union-Find 算法，也就是常说的并查集算法，主要是解决图论中「动态连通性」问题的。名词很高端，其实特别好理解，等会解释，另外这个算法的应用都非常有趣。
上一篇：无向图的实现 下一篇：深度优先遍历 根据描述，很容易实现图的深度优先搜索： public class DepthFirstPaths { private boolean[] marked; //标记已经访问过的结点 private int count; public DepthFirstPaths(Graph G,int s) {//以s作为起始顶点深度优先遍历无向图G marked = new boolean[G.V()]; dfs(G,s); //调用真正的深度优先遍历
有N个城市（编号1到N）和M条双向道路（编号1到M）。道路 i 连接城市 A 和城市 B 。
在计算机科学中，并查集（英文：Disjoint-set data structure，直译为不交集数据结构）是一种数据结构，用于处理一些不交集（Disjoint sets，一系列没有重复元素的集合）的合并及查询问题。并查集支持如下操作：
关于并查集的题目不少，官方给的数据是 30 道（截止 2020-02-20），但是有一些题目虽然官方没有贴并查集标签，但是使用并查集来说确非常简单。这类题目如果掌握模板，那么刷这种题会非常快，并且犯错的概率会大大降低，这就是模板的好处。
上一篇：加权无向图的实现 加权无向图----Prim算法实现最小生成树 数据结构： 用一条优先队列将边按照权重从小到大排序 用union-find数据结构来识别会形成环的边 用一条队列来保存最小生成树的所有边 Kruskal算法的计算一个含V个顶点和E条边的连通加权无向图的最小生成树所需空间与E成正比，所需时间与ElogE成正比（最坏情况）。 方法：将边都添加进最小优先权队列中，每次从中取出最小的边，检查会不会与已经选出的边构成环（使用union-find算法），如果构成环，则弃掉这条边，否则将这条边加入最
并查集（Disjoint set或者Union-find set）是一种树型的数据结构，经常使用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。
并查集（Union Find），从字面意思不太好理解这东西是个啥，但从名字大概可以得知与查询和集合有关，而实际也确实如此。并查集实际上是一种很不一样的树形结构，用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。
生成树的定义：对于一个图G，获取G的边使得所有的顶点都连接到。最小生成树(MST Minimun spanning tree):给定图G(V,E),以及对应的边的权重，获取一颗总权重最小的生成树。
班上有 N 名学生。其中有些人是朋友，有些则不是。他们的友谊具有是传递性。如果已知 A 是 B 的朋友，B 是 C 的朋友，那么我们可以认为 A 也是 C 的朋友。所谓的朋友圈，是指所有朋友的集合。
在 LeetCode 上有一道题 LeetCode-547 朋友圈[1]，题目大意是这样：
并查集定义 在计算机科学中，并查集是一种树型的数据结构，用于处理一些不交集（Disjoint Sets）的合并及查询问题。有一个联合-查找算法（union-find algorithm）定义了两个用于此数据结构的操作：
在计算机科学中，并查集是一种树型的数据结构，其保持着用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。有一个联合-查找算法（union-find algorithm）定义了两个操作用于此数据结构：
定义union-find算法API： public class UF{ UF(int N) 初始化N个触点 void union(int p,int q) 在p和q之间建立连接 int find(int p) p所在的分量的标识符 boolean connected(int p,int q) p和q同在一个分量中则为
Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
最近又有不少老铁在后台留言说，想进大厂，但是算法不好。最近我整理了一份刷题实录，这份刷题实录，也让我进了心仪的大厂。现在开放分享给大家。希望对大家有所帮助。
今天跟大家分享一个算法，如题union-find。这个算法要解决的就是一个动态连通性问题，什么是动态连通性呢？首先是连通性，给出两个对象，可以判断两个对象是否相连；再有就是动态，如若给出的两个对象不相连，我们可以将他们连起来，于是连通的对象发生了变化，体现了动态。举个栗子来说，就像判断两个计算机能否实现通信，就是判断他们是否能够通过现有的线路相连，进行通信，如果不能通信就需要通过其他手段，如增加物理线路，增加路由等来使得两个计算机实现连接。在下边的叙述中，为了方便起见，我们把一个一个对象，或者一个一个计算机称为触点，相连的几个触点整体称为连通分量（简称分量）。
今天我们继续来解读《算法》这本书，我将会按照书中的顺序来依次来介绍算法。今天介绍的是本书的第二个算法——并查集。
有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。
通常来说，这个步骤在每次使用该数据结构时只需要执行一次，无论何种实现方式，时间复杂度均为O(N)。
没想到有一天我也能搞懂并查集，orz......实际上本文算是《Algorithms》一书的读后感
今天分享到的是一种相对冷门的数据结构 —— 并查集。虽然冷门，但是它背后体现的算法思想却非常精妙，在处理特定问题上能做到出奇制胜。那么，并查集是用来解决什么问题的呢？
一列已知的步长为 1 且从 0 开始依次递增的整数序列，对于成对整数 p 和 q ，即认为 p 与 q 相连。“相连”是一种等价关系，即具有自反性p 和 p 是相连的。、对称性如果 p 和 q 是相连的，那么 q 和 p 也是相连的。与传递性如果 p 和 q 是相连的且 q 和 r 是相连的，那么 p 和 r 也是相连的。。现程序从输入中读取一对整数 p 和 q ，假设 p 和 q 都存在于已知序列中，若序列中对应整数相连，则不做操作，若序列中对应整数不相连，则将他们相连，并将 p 和 q 输出。
有一个二维的面板，上面由”X”或者”O”填充。现在要求将被”X”包围的”O”都改成”X”。
我们之前讲的树结构，都是由父亲节点指向孩子节点，而并查集却是由孩子指向父亲的这样一种数据结构。
并查集是我暑假从高手那里学到的一招，觉得真是太精妙的设计了。以前我无法解决的一类问题竟然可以用如此简单高效的方法搞定。不分享出来真是对不起party了。（party：我靠，关我嘛事啊？我跟你很熟么？） 来看一个实例，杭电1232畅通工程 首先在地图上给你若干个城镇，这些城镇都可以看作点，然后告诉你哪些对城镇之间是有道路直接相连的。最后要解决的是整幅图的连通性问题。比如随意给你两个点，让你判断它们是否连通，或者问你整幅图一共有几个连通分支，也就是被分成了几个互相独立的块。像畅通工程这题，问还需要修几条路，
导读： 奥地利符号计算研究所的Christoph Koutschan博士在自己的页面上发布了一篇文章，提到他做了一个调查，参与者大多数是计算机科学家，他请这些科学家投票选出最重要的算法，以下是这次调查的结果，按照英文名称字母顺序排序。 1. A* search algorithm Graph search algorithm that finds a path from a given initial node to a given goal node. It employs a heuristic est
不少搞IT的朋友听到“算法”时总是觉得它太难，太高大上了。今天，跟大伙儿分享一个比较俗气，但是却非常高效实用的算法，如标题所示Union-Find，是研究关于动态连通性的问题。不保证我能清晰的表述并解释这个算法，也不保证你可以领会这个算法的绝妙之处。但是，只要跟着思路一步一步来，相信你一定可以理解它，并像我一样享受它。
「单调栈」首先是一种基于栈的数据结构，只不过通过栈来维护的是单调递增或单调递减的数据。入栈和出栈都是操作栈顶。对于每一个元素都只有一次入栈和出栈的操作，因此时间复杂度为O(N)。
最近，北大学霸的LeetCode刷题笔记在GitHub上疯传！已经有不少人靠它手撕算法题，拿下了字节、腾讯等大厂offer！
基础数据结构 例题 例题1 UVa11995 AC I Can Guess the Data Structure! ADT 题解 例题2 UVa11991 AC Easy Problem from Rujia Liu 排序或者善用STL 题解 例题3 LA3135 AC Argus 优先队列；模拟 题解 例题4 UVa11997 AC K Smallest Sums 优先队列；有序表合并 题解 例题5 LA3644 AC X-Plosives 并查集
在一些应用问题中，需要将 n 个不同的元素划分成一些不相交的集合。开始时，每个元素自成一个单元素集合，然后按一定的规律将归于同一组元素的集合合并。在此过程中要反复用到查询某一个元素归属于那个集合的运算。适合于描述这类问题的抽象数据类型称为并查集(union-find set)。
生成树：给定无向图G=(V,E)，连接G中所有点，且边集是E的n-1条边构成的无向连通子图称为G的生成树(Spanning Tree)，而边权值总和最小的生成树称为最小生成树（Minimal Spanning Tree,MST）。
Caffe - 显存优化 1. Caffe - memory multiloading 功能 原文 - Squeezing Memory out of Caffe Caffe 的一个优化版本 - caffe-yjxiong. 测试了一下, ResNet101 相对于官方 caffe, 能够明显节省显存占用, batchsize 可以增加很多. 显存优化的 Caffe 主要实现的功能: memory multiloading 在深度网络训练和测试时,可以显著地节省内存. 训练时,节省一半内存; 测试时,
在面试前一周，我刷了很多道算法，分类刷，有些是做过的，因为我是面试C++相关岗位，除了leetcode与剑指offer相关的算法，还需要手撕一些智能指针呀，单例模式呀、字符串呀、LRU、排序算法等等。
并查集需要建立映射关系，那么下面的代码是建立映射关系的一种方法（并查集的实现不采用这种方法）。
我们可以用vector存名字数组里面的数据，那下标就可以做它们的编号，那这样用编号找名字是很方便的，编号是几，就找下标为几的元素就行了。 但是名字找编号就有点麻烦，所以我们可以借助map给名字和编号建立一个映射关系。
在一些应用问题中，需要将n个不同的元素划分成一些不相交的集合。开始时，每个元素自成一个单元素集合，然后按一定的规律将归于同一组元素的集合合并。在此过程中要反复用到查询某一个元素归属于那个集合的运算。适合于描述这类问题的抽象数据类型称为并查集(union-find set)。
本文转载自July CSDN博客：http://blog.csdn.net/v_JULY_v/archive/2011/03/07/6228235.aspx
下面是一些比较重要的算法，原文 罗列了32个，但我觉得有很多是数论里的或是比较生僻的，和计算机的不相干，所以没有选取。下面的这些，有 的我们经常在用，有的基本不用。有的很常见，有的很偏。不过了解一下也是好事。也欢迎你留下你觉得有意义的算法。（注：本篇文章并非翻译，其中的算法描述 大部份摘自Wikipedia，因为维基百科描述的很专业了）
奥地利符号计算研究所（Research Institute for Symbolic Computation，简称RISC）的Christoph Koutschan博士在自己的页面上发布了一篇文章，提到他做了一个调查，参与者大多数是计算机科学家，他请这些科学家投票选出最重要的算法，以下是这次调查的结果，按照英文名称字母顺序排序。 1、A* 搜索算法——图形搜索算法，从给定起点到给定终点计算出路径。其中使用了一种启发式的估算，为每个节点估算通过该节点的最佳路径，并以之为各个地点排定次序。算法以得到的次序
【新智元导读】 奥地利符号计算研究所（Research Institute for Symbolic Computation，简称RISC）的Christoph Koutschan博士在自己的页面上发布了一篇文章，提到他做了一个调查，什么是计算机科学中最重要的算法？参与者大多数是计算机科学家。以下是这次调查的结果，按照英文名称字母顺序排序。 A* 搜索算法——图形搜索算法，从给定起点到给定终点计算出路径。其中使用了一种启发式的估算，为每个节点估算通过该节点的最佳路径，并以之为各个地点排定次序。算法以得到的次
奥地利符号计算研究所（Research Institute for Symbolic Computation，简称RISC）的Christoph Koutschan博士在自己的页面上发布了一篇文章，提到他做了一个调查，参与者大多数是计算机科学家，他请这些科学家投票选出最重要的算法，以下是这次调查的结果，按照英文名称字母顺序排序。 1. A*搜索算法 图形搜索算法，从给定起点到给定终点计算出路径。其中使用了一种启发式的估算，为每个节点估算通过该节点的最佳路径，并以之为各个地点排定次序。算法以得到的次序
导读：奥地利符号计算研究所（Research Institute for Symbolic Computation，简称RISC）的Christoph Koutschan博士在自己的页面上发布了一篇文章，提到他做了一个调查，参与者大多数是计算机科学家，他请这些科学家投票选出最重要的算法，以下是这次调查的结果，按照英文名称字母顺序排序。
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
ICP备案
对象存储
腾讯会议
实时音视频
