Open caibirdme opened 4 years ago
caibirdme
commented
4 years ago Evaluate Division
这道题最朴素的做法就是建立双向边，每次dfs或者bfs找一条路。但是更好的方法其实是利用并查集。
对于a/b=2，可以建立即b的father是a且权值是2。b/c=3，b是c的father，但是利用路径压缩，a是c的father且权值是6。
查询时，b/c == 1/(a/b) * (a/c)，这样在压缩完以后，基本上利用O(1)的时间就能查出结果了
caibirdme
commented
4 years ago Redundant Connection II 无向图和有向图对于这道题有啥区别？本质区别就是无向图可以删环上任意一条边，而有向图需要分情况讨论。有向图中不一定存在环，可以把有向图想象成一个多叉树，多出来的边分为两种情况：
对于情况一，这种情况就存在环，但是细分又有两种情况：
这种是从树的结构来划分的，不过其实可以发现，本质问题在于存不存在入度为2的点，而不是有没有环。除非是子树指向了原来的根节点，否则其它case都存在入度为2的点。
如果不存在入度为2的点，那么我们可以删除环上任意一条边，因此我们可以把它当做无向图处理。利用并查集，如果一条边的两个顶点都在同一个集合，那么这条边肯定就是环上的一条。 如果存在入度为2的点A，有两条边x和y都指向它，如果从根到A的路径上那条边为x，如果存在环，那么我们需要删的就是y。这样我们可以保证，如果有环，我们删除的一定是环上的边。但是如果不存在环，本质上两条边都可以删，也就是说从根有两条路径能走到点A。假如我们第一次遍历到A记录的边是x，这时候根据题意需要看x和y谁后出现在输入数据中，然后删除后出现的。 然而问题是，我们只知道有没有入度为2的点，并不知道是否存在环！！因此从根开始遍历这种方法实际上不适用。不过既然已经确定了要删的边是这二者其一，那么我们可以先删除出现靠后的那条边。如果删错了，那么自然就应该删另一条边。因此，当我们删一条边之后，如果之前有环，那么删完之后就应该没有环了。如果之前没有环，那么删完之后依然没有环。因此，我们删一条边之后只需要验证有没有环即可。这时就可以按无向图的处理方式，使用并查集了
这道题分析起来复杂，但是实际做起来很简单。如果细想可能会发现很多case导致耽误比赛时间，因此要多理解无向图和有向图的区别，在比赛时能够快速使用结论，而不是现推。
caibirdme
commented
4 years ago 发现了最短路Dijstra算法+堆优化的一种简便实现，记录一下。以前自己实现的时候非常复杂，因为当时的做法是，每次从堆里取出dist最小的节点，然后用它去更新其它节点的dist。由于其它节点的dist被更新，因此它在堆中的顺序就需要调整。所以除了堆本身，我们还需要一个数据结构能通过node_id快速找到该node在堆中的位置，然后向上或者向下调整，并且同步更新索引表。这个实现起来相当的麻烦，并且这种数据结构想用Rust来写，简直难比登天！
有一种简便方法就是，转变一下我们对堆的定义。前面的实现方式，我们堆中保存的都是目前为止所有点的最短距离。如果存储的是这样的数据，那么通过一个节点更新之后，某些点的最短距离就会变化，从而使得堆需要跟着调整。那么我们可以改变一下对堆的使用，让堆存储“通过某些节点更新后，节点x能到达的距离”。当我们把通过节点更新别的节点的距离时，我们直接把更新后的(new_distance, node_id)放到堆中，那么通过不同节点对于同一个点的更新可能存在几个不同的值，由于heap的特性，会先取出最小的那个。
这种实现方式虽然简单，但是有个问题，对于稠密图，一共n个点，假如所有点都两两相连，0扩展出n-1个点，1扩展出n-2个，2扩展出n-3个，…。极端情况下堆中可能会有(1+n-1)*(n-1)/2个元素。如果n很大，比如10^4，那么空间会消耗巨大，但是对于小规模数据，这种实现方式就比较简单。
caibirdme
commented
4 years ago Couples Holding Hands 这道题是一个图论的贪心，贪心策略其实比较直观但是如果是比赛时比较难以证明。假设板凳A有坐了组x和组y的两个人，那么对于板凳A，一定是进行一次交换，从其它地方换一个组x或者组y的人过来（比如就换x过来），然后板凳A就配对成功，y被放到另一个板凳B。假设B原本就是y，现在换了个y过来，那么就不用换了，假如以前不是y，是z，那么还得想办法从其它地方换一个y或者z过来。 那么交换的尽头是啥呢？当一次交换完成时，涉及到的两个板凳都匹配成功，那么这一轮交换就结束。 假如板凳A需要从板凳X换一个人过来让板凳A匹配，我们可以想象成A点到X点有一条双向边。基于这种方式建图之后，每一条边就相当于一次交换，能够使一个点匹配成功。如果存在一个环，那么N个点沿着这个环，只需要N-1次交换，这就是最少的交换次数。所以最终我们可以把问题转换成求图中有几个环。最简单的办法就是利用并查集，最后看有几个集合存在。
caibirdme
commented
4 years ago Find Eventual Safe States 这道题其实就是确定图中哪些节点能够走到环中哪些不能. 我的解法是DFS,直接从某个点开始进行遍历,然后遍历过程中确认是否走到了访问过的点(环). 利用ans[node]来做记忆化搜索,总体时间复杂度可以控制到O(n+E)级别 看题解之后发现更简单的其实是拓扑排序. 这里需要总结的一个点就是,涉及到环的题目,大多数都和拓扑排序有关.因为拓扑排序本身就是用来解决这个问题的.首先应该从拓扑排序下手,而不是直接顺着题目想,DFS这类解法一般都是最后再考虑
caibirdme
commented
4 years ago 小结: 图论题目一般是属于比较难的题目, 而面试时考察的图论都相对简单. 通过LC上的题目总结,一般图论有以下几种基础题型:
图论题目的难点在于,你得看出来题目是一个图论题.然后再使用对应的算法.
最短路有几种比较经典的算法, 每种都有一些特点和适用场景:
| 算法 | 适用场景 | 不适用场景 | 复杂度 |
|---|---|---|---|
| Dijstra | 单源最短路 稠密图 | 含负权边 | nlogn(堆优化) |
| Floyd | 多源最短路 | 负环 | n^3 |
| Bellman-Ford | 单元最短路 可处理负环 | N*M | |
| SPFA | 单源最短路 | 稠密图不如Dijstra | < N*M |
其中, 大部分时候选SPFA都属于比较好的选择,除非题目的目的就是让你写Dijstra的堆优化 Floyd需要重点理解 判断负环的题目需要SPFA和Bellman-Ford,也需要掌握
通过统计节点的入度或者出度,每次选择度为0的点,删除改点然后更新相关点. 拓扑排序可以用来找环, 凡是和环相关的题目,先看能不能拓扑排序
并查集是很多图论题目需要使用到的工具算法, 用于判断节点是否在同一个连同块中. 并查集同样也可以用来找环, 更一般地,它是用来找连通块
主要是两种算法, Kruscal+并查集, 以及prime算法. 同样的,由于prime基于和Dijstra类似的贪心假设,因此不能处理边权值为负的图, Kruscal+并查集基本上能做到ElogE的复杂度(E是边数)
caibirdme
commented
4 years ago Floyd算法 其实就是动态规划, f[k][i][j]表示, 从i走到j, 中间只经过节点1..k的最短路. 所以有:
f[k][i][j] = min(f[k-1][i][j], f[k-1][i][k]+ f[k-1][k][j])首先理解为什么这么划分状态以及转移是可行的.
f[k-1][i][k]+f[k-1][k][j]状态方程好理解,但是为什么这么做是对的呢?假设i是0,j是10,我们划分状态是按节点数从小到大划分,但是不需要care节点的连接状态吗?我如果枚举k是(0..10).shuffle(), 这样可行吗? 比如说,假如最优解是0先到9,再到1,再到8,再到2...最优路径类似于0->9 -> 8->2->10,那么上面枚举方式能构造出这样的解吗? 实际上跟k的枚举顺序没关系, 因为k只是每次新增的一个用来松弛的点.i到j可能已经用别的点松弛过了,但是只要保证i..j没有用k松弛过,那么k就可能带来新的可能性.
caibirdme
commented
4 years ago Find the City With the Smallest Number of Neighbors at a Threshold Distance 这是一个非常直观的计算多源点最短路的题目, 先计算出所有点互相的最短路,然后枚举每个点,看它到哪些点的距离小于等于限制,最后找到最小的那个即可.
Course Schedule 在有向图里找环，方法就是拓扑排序。每次找到入度为0的点，删除该店及对应的边。如果最后所有点都删除了，则无环，否则有环。