所有代码详见:https://github.com/jingminglake/Leetcode
总体思路
- 并查集是什么
图的信息就是点集合 + 边集合。
并查集在一开始就是表示点集合,但是这些点是一群孤立的点,之后就是通过union操作+边集合信息,把点连接起来,在这种连接的过程中, 可以使用find操作来知道当前的两个点之间是否是连通的。
- 并查集的具体实现
并查集使用一个hashmap来装所有结点,以及该结点对应的总领导(key是结点,value是结点对应的总领导)。这张表叫parent、father表或者boss表。
一开始全是孤立点的时候,每个结点的总领导就是自己。根据边进行点连接的时候,就相当于两家公司进行合并,此时任意选其中一个公司的总领导作为合并后的总领导。 具体过程就是:先使用find操作找到两个结点的总领导ceo1,ceo2,然后把一个总领导(例如ceo1)的总领导变为ceo2。如果find(A) == find(B),那么说明A和B在本来就是同一家公司工作。
find操作,可以找到一个结点的总领导(CEO)结点,而并不关心中间领导,由于信息是实时更新的,因此parent[x]并一定就是x的总领导,而是要检查parent[x]是不是还存在领导。 而如果parent[x] == x的时候,也就是ceo的领导是自己的时候,那就是遇到终止条件。 所以常规解法是一步步向上去找,消耗时间O(N),代码如下: int find(int x) { if (parent[x] == x) { return x; } return find(parent[x]); }
但是,实际上,在找总领导的过程中,可以实时更新所有查询路径上的点的总领导。这样,find操作时间从O(N)优化到接近O(1)。 优化代码如下: compressed_find(){ if (parent[x] == x) { return x; } return parent[x] = compressed_find(parent[x]); }
union操作就是两家公司合并的操作。操作过程就是,先find到两家公司的CEO,然后把其中一个指向另一个,代码如下: void union(int a, int b) { int root_a = find(a); int root_b = find(b); if (root_a != root_b) { // 如果不属于同一公司 parent[root_a] = root_b; } }
union操作时间也是O(1)。
所以,并查集的模板就是:
class UnionFind {
int find(int x);
void union(int a, int b);
vector
- 并查集使用情况
关于点的合并或者点的连边,关于集合的合并,查询,一般用并查集。但注意并查集不提供删边操作。
- 并查集其他技巧:
(1)求连通区域的个数。并查集可以加一个变量来表示公司的个数(连通区域的个数)。初始时候该变量为元素个数,每次union操作时候,只要两个点不属于一个公司时候,将变量减1。
也可以在建立连通图后计算:通过遍历每一个节点x,看其parent[x]是否等于自己,如果相等,算作一个区域数。 同理,想要知道每片连通区域的具体结点信息,可以遍历parent数组,将区域的parent结点作为key,将子节点存入指向的vector。
(2)知道某些点之间互相连通的时候,可以O(n)时间建立连通,原理就是把其他所有点连接到第一个点上,那么自然所有点就连通了。
(3)并查集可以加一个size数组来记录以key为总领导的公司的员工数量。size数组只有在该key确实是CEO时候去查才有意义,否则没意义。
具体题目
261. Graph Valid Tree
题意:验证图是不是树,给出的是结点以及结点直接连接的信息。给出的图信息是点,加边信息。
解:树的概念:树是连通且不存在回路(环)的图,也意味树有一个性质,就是边的数量等于顶点数量减1。
所以验证图是不是树要满足两个条件,一个是图上的任意两点之间连通,第二是图不存在环。判断无向图是否有环,只需要建立标记数组,只要访问回原来结点,那么就有环。
还有一个可以不检测有环的方法:只需要判断边的数量是不是顶点数量减1就可以。这样只需满足这一条件,再加上图是连通的,就满足图是树了。
方法一:dfs。首先再次说一下,dfs本质就是树结构的回溯,对于图,也就是选择一个作root。 对于无向图,存在环的判断就是:遍历时候一旦遇到已经经过dfs处理访问过的结点,那么就存在环。但是其中有一个特例,因为两个结点互为邻居,所以加入邻居结点的时候,由于父节点一定是已经访问过,所以常规dfs情况下,只需要去掉访问过的结点就行了,但是判断环的dfs中我们不能知道一个vistited结点是因为有环所以造成找到visited结点还是因为天生的找到父节点的情况,所以我们改变进入下一层的条件:明确的指出,排除掉邻居是父节点的情况。
方法二:bfs。分为三种状态,正在访问状态,未访问状态,和访问结束状态。bfs的时候,如果邻居结点都被压栈,那么状态为已访问。结点进入队列后标记为正在访问状态。结点处理邻居结点的时候,如果邻居结点处于正在访问状态,那么返回false;如果是已访问状态,那么不用压栈。
方法三:并查集。对于一个pair,看两个连接的点在已构建出的图中是否属于同一个公司,如果属于同一个公司,那么说明他们除了相互连接外,还有其他路径连通,所以就是存在环。
另外:判断是否连通,就看边的数量是不是顶点减1,如果是,那么说明是连通的。
此题还可以把方法一、二进行优化,比如一开始就看边和点的关系是不是满足tree,不满足直接返回false,如果满足,那么不可能存在环,问题就简化为判断图是否是连通的。
721. Accounts Merge
题意:找到所有人和其对应的邮箱的列表,人名不是id,邮箱才是id。
解:此题是图的问题,如果不转化为图(也就是不转化为合适的数据结构),而只是扫描的话,就会发现很难将当前处理的结果存入之前的结果。
所以还是利用合适的数据结构来解题会比较舒适。首先,将email作为id建立关系图,处于同一账户元素里面的email是互相连通的,但是谁作为第一邻居,其实是无所谓的,简单起见,把第一个email和剩余email相连,这样所有email之间都连通了。这样扫描一遍所有账户后,就得到了email的邻接表表示的图。
另外,第一遍扫描所有账户的时候,新建hash表,建立email指向用户名的映射,这样方便找到email对应的用户名。另外,取用户名也可以放在下一次扫描所有账户的时候。
方法一:使用并查集。第一遍扫描所有账户将连通的email连通,第二遍扫描并查集hashmap时候把每个结点的所在的CEO的name取出作为key,形成map,最后再把map转成vector即可。
方法二:dfs。第一遍扫描所有账户将连通的email连通(每个账户其余email均与第一个email相连),然后,进行dfs,使用visited数组来记录结点是否访问,dfs起点是每个账户第一个email。
684. Redundant Connection
题意:检测图是不是树,给出的图多出了一条边,因此形成了环,此题给出的边的链接是小节点连接到大节点。求多余的那条边,如果有多种选项,那么最后一个多余的pair做答案。
解:此题使用并查集做,也就是说并查集也可以检测图中是否有环。对于给出的边,尝试链接到原来的图上面,先检查当前两个点在原图中是不是属于一个结点,如果是,说明两个点在未加入前已经是连通的,因此如果再加入那么必定会形成环,也就是多余的边。
如果使用dfs,那么先建图,然后检测环是不行的,因为找不到最后一个pair。一个改进的方法就是,一次加一条边到图上,然后在之前检测当前加入的边的两个顶点是不是已经连通了,已经连通的话就是答案,思路和unionfind一致。
685. Redundant Connection II
题意:与684的区别是,此题是有向图,而且有向图表面的那种环也算环。
解:此题比较难想到通用解题思路。所以从给出的例子里面找规律,看能不能总结出要求删除的边的特点。特点就是:(1)如果一个结点存在两个入度,那么两个入度中的一个必作为答案。其中具体哪个作为答案分两种情况:一种是如果去掉其中一个,剩下的图形成不了环(使用类似无向图的unionfind检测,一边加,一边检测),那么说明删除的是答案;第二种情况是,如果去掉其中一个,剩下的还是存在环,那么另一个是答案。(2)如果所有节点都是一个入度,但是存在环,此时使用类似无向图的unionfind检测解题就可以。
128. Longest Consecutive Sequence
题意:找出数组的最长大小连续(consecutive)的序列的长度,例如[100, 4, 200, 1, 3, 2]的最长大小连续的序列是[1, 2, 3, 4],长度是4。
解:此题思想是union find,扫描数组,当我们扫描到1的时候,那么我们会先看他的邻居结点0和2是否已经在之前被扫描过,如果扫描过,那么把自己链接到原来的那一片连通的区域中,也就是说,原来一片区域的总结点数要加1。实际上,这片区域就是一个区间,我们可以使用一个技巧,也就是只使用区间左右端点来记录区间的大小,因为如果扫描的一个点落在了区间以内,那么这个点并不会使得区间的大小(也就是连续序列的长度)变化,而只可能是点落在区间左端点之前,或者右端点之后才会使得区间大小加1。
扫描数组,使用hash表记录每个元素作为所属区间边界的长度,对于元素num,先看num有没有处理过,如果没有处理过才进行处理,也就是说处理之前先查表,如果存在了,那么就直接continue。因为存在了,说明num作为边界已经处理过了,现在是必属于某个区间里面的,所以没有必要更新了。
如果num存在,那么看num-1和num+1是否存在。
如果num-1和num+1都不存在,那么num对应长度为1,存入hash表。
如果num-1存在而num+1不存在,说明num-1所在区间可以更新1,num-1所在区间本来右边界是num-1,现在更新的区间的右边界显然是num,那么在看num-1所属区间的左边界在哪,显然,hash[num-1]就是区间大小,也就是说左端点大小是num - hash[num - 1],其在hash表中对应的值应该加1。
同理处理num-1不存在而num+1存在的情况。
当num-1和num+1都存在的时候,要把最终长度更新到两边的边界,num标记为已访问就可以了,因为我们知道,每次其实是一个一个元素的加到hash表中的,也就是说,加入num之前,num-1和num+1所在的区间的每个元素都被访问过了。
扫描过程中记录更新中可以产生的最大值,作为结果返回。
803. Bricks Falling When Hit
题意:二维矩阵表示,0表示空,1表示砖。二维矩阵第0行看作天花板。先给出这样一个矩阵,然后在给出一个二维数组坐标,表示打掉该坐标处的砖。现在要求的是每次掉落的砖,砖会掉落如果它不与天花板连通。
解:思路一:并查集。反着来添加打掉的坐标,每次当作添加砖,然后看每次有多少新砖可以连通到天花板。
具体做法是:首先,计算出初始状态的所有点的连通性:先去掉准备打掉砖的坐标,然后把剩余的砖,进行二维数组的扫描,每次考虑当前坐标和他的左边和上边的点,如果当前点和左边的点都是砖,那么进行一次union操作。两个parent合并的时候,如果有第0行的结点,那么就选其作为parent结点。
其次,倒着加入打掉的坐标,如果四个方向上有1,那么union操作,然后看新的图有多少连通点,减去之前状态的连通点就可以知道这一步连通了多少个新点,也就是会掉多少点。 其中计算连通点有一个技巧,就是把所有的顶层的点和一个额外空间进行连接,在把连通点个数记录到额外空间对应的值,这样可以一次查出所有连通点数量。