安全状态

思路

建图后,需要判断一次深搜路径上有无重复点出现,并用涂色法记录整条路径上的安全或者不安全状态。

Read more

二分图匹配

二分图匹配

二分图匹配是个经典问题——两组节点在图上尽可能的匹配。

匈牙利算法以不断寻找增光路的方式,寻找更多的匹配;

思想如下:

  1. 从未匹配的点c开始寻找链接的点v,如果v也是未匹配,则匹配成功。如果该点已经匹配了u,则递归尝试让u匹配其他节点。
  2. 如果v匹配失败,那就找找c的其他点。

题解参考

Read more

割点算法

割点算法Tarjan

割点算法 引入了建立在DFS生成树的遍历节点的时间戳概念,如果一个节点u的子节点v可以找到一条不经过u以外的路径到达u的祖先,那么显然有一条通路可以回到u的祖先。反之,如果存在v找不到这么一条路径回到u的祖先,那么显然u是一个割点,他分割了v所在的子树和其他子树(如果u不是根的话,包括祖先所在子树)。

image-20210509113600747

那么一个割点有多少子树呢?
首先,一个割点的对应的v是独立在各个子树的吗?是的,如果存在v1v2都找到路径,且在一个子树中,那么必然有v1可以通过v2找到u,那么在DFS搜索的时候,必定会一次遍历v1v2。所以每个割点对应的子树只会搜索到一个v
扩展一下, 那么经过去掉割点的图最多有几个连通块?

Read more

882. Reachable Nodes In Subdivided Graph

思路:

subdivision nodes可以化为路径的长度,将此问题转化为可以用dijstra求解的问题。

每次遍历到最新最短的节点都可以进行求出此点相连的边的可以累加subdivistion nodes的个数,但是需要控制重复累加比较麻烦。最后采用记录下每条边可到达的点,最后统一累计即可。

Read more