\(\mathtt{0}\) 前言
本来想叫“OI 中的一些杂技”，但考虑到一些东西可能很实用，遂改成了现在的标题。
因为学的知识点有点杂，所以这篇博文啥都会讲点，可能会有一些 trick 和有趣的题。
写个自己看的，不保证能看懂。
\(\mathtt{1}\) Tarjan 及其相关
\(\mathtt{1/1}\) 桥
对于一张无向连通图 \(G\)，对于其中某条边 \(e\)，如果 \(G-e\) 不联通，那么 \(e\) 就是 \(G\) 的一个桥。
考虑对 \(G\) 进行 DFS，我们会得到 树边 和 返祖边 两种类型的边，其中树边为位于 DFS 树上的边，返祖边为通过这条边能够返回到祖先的边。
考虑没有返祖边的情况，此时 \(G\) 是一棵树，割掉其中任意一条边都会导致图不连通，所以 \(G\) 里面的所有边都是桥。
如果有返祖边，我们割掉一条边后仍然可能通过返祖边返回，所以不能套用之前的方法。
处理这个问题的方法是 Tarjan 的核心：\(\mathrm{dfn}-\mathrm{low}\)
我们考虑维护每个点的 DFS 序 \(\mathrm{dfn}_i\)，那么两个点的 DFS 序关系就代表它们被访问的先后顺序，于是 DFS 树上祖先的 \(\mathrm{dfn}\) 一定小于子节点的 \(\mathrm{dfn}\)
那么我们就可以进一步对每个节点 \(x\) 维护“不经过父边，它能到的最小的 \(\mathrm{dfn}\) 值” \(\mathrm{low}_x\)，考虑维护它。对于它连接的所有非父边的边，我们分类讨论：如果该边为树边（对应点 \(i\) 还没被遍历），我们遍历它，同时将当前点的 \(\mathrm{low}_x\) 用 \(\mathrm{low}_i\) 更新；如果该边为返祖边（对应点 \(i\) 已被遍历），我们直接将 \(\mathrm{low}_x\) 用 \(\mathrm{dfn}_i\) 更新。
遍历完后，如果当前点 \(x\) 满足 \(\mathrm{dfn}_x=\mathrm{low}_x\)，则说明它能到的 DFS 序最小的点就是它本身，于是它的父边即为桥。
\(\mathtt{1/3}\) 强连通分量
我们称有向图 \(G\) 强连通，当且仅当 \(G\) 中任意两个节点均联通。
强连通分量为极大强连通子图。