缩点与强连通分量
Kosaraju 算法求强连通分量原理遍历两次 DFS，第一次遍历的时候按后序存储到数组里面，做记录。 第二次，从后往前按之前记录的数组，遍历所有这次没有被访问的点。证明云剪贴板 - 洛谷 | 计算机科学教育新生态 (luogu…
TAG
图论
使用这个标签归档的内容。4 篇内容
↗
拓扑排序
前置知识DAG，是有向图（有向无环图）的简称。拓扑排序的定义如果 DAG 的一个遍历序列满足：每个点都访问了一遍。对于每个便，出发节点在目的地节点的前面输出。求拓扑排序定义 $d_i$ 为第 $i$ 个节点的入度。用邻接表储存一…
欧拉图相关知识点学习笔记
[label color = "orange"]图论[/label]欧拉回路欧拉回路的定义是：对于一个图，如果从一个点出发，遍历所有的边后回到出发的那一个点，那么这个图就含有欧拉回路。欧拉回路其实和小学时学习的一笔画问题有关系。…
搜索 & 图的储存和最短路算法
搜索DFS这种方法可以概括为：不撞南墙不回头，回过头来继续撞。DFS，深度优先搜索，顾名思义就是每次递归到最深，然后回溯。我们一般用递归函数实现 DFS。例题：用 DFS 求最短路：#include <bits/stdc+…