相关定义
若有向图的 \(u, v\) 两点互相可达，则称 \(u, v\) 强连通。满足任意两点强连通的有向图为 强连通图。有向图的极大强连通子图称作 强连通分量（SCC）。
以下讨论时默认图为有向弱连通图（弱连通即将有向边看作无向边时连通）。
DFS 树
对于有向图，按照任意顺序对结点进行 DFS，得到 DFS 森林，DFS 树上的点称作树边。显然每棵 DFS 树内部的结点不强连通。
定义 DFS 树中从祖先指向后代的非树边，称为 前向边；从后代指向祖先的非树边为 返祖边；两端无祖先后代关系的边为 横叉边。
前向边不影响可达性。返祖边 \((u, v)\) 会使得 \(v\) 到 \(u\) 路径上的所有点之间强连通，且返祖边会减少时间戳。
对于横叉边，显然应该有 \(dfn(v) < dfn(u)\)，因此也减少时间戳。进一步，若 \(dfn(v) < dfn(u)\)，则 \(v\) 可达 \(u\) 当且仅当 \(v\) 可达 \(\operatorname{lca}(u, v)\)。
SCC 求法
令 \(dfn_u\) 为 dfs 序，\(low_u\) 为 \(u\) 经过树边与返祖边能到达的最小时间戳。则当 \(dfn_u = low_u\) 时以 \(u\) 为根的 dfs 子树中的点构成一个强连通分量。
void tarjan(int u) {dfn[u] = low[u] = ++ timestamp;stk[++ top] = u, vis[u] = 1;for (auto v : G[u]) {if (!dfn[v]) {tarjan(v);low[u] = min(low[u], low[v]); } else if (vis[v]) low[u] = min(low[u], dfn[v]);}if (low[u] == dfn[u]) {++ scnt; int x; do {x = stk[top]; col[x] = scnt; top --; vis[x] = 0;} while (x != u); }
}
例题
P3387
我们将每个 SCC 缩成点，点权为 SCC 内部的点权和，进行拓扑排序 DP 即可。
注意到根据上述过程找出 SCC 后得到逆拓扑序，所以不用特别再处理了。
P3436
如果存在自环切该点能够到达 \(n + 1\) 答案有 \(\infty\) 个。如果存在大小大于 \(1\) 的 SCC 连通 \(n + 1\) 那么 SCC 内的所有点答案都是 \(\infty\)。
边 DP 求答案边找这个即可。
P7737
一个强连通分量中的点显然可以互相到达，所以先缩点，缩成一个 DAG。
会发现 DAG 其实不是很好做，考虑题目给出的特殊结构，若 \(x \to z, y \to z\)，则存在 \(x \to y\) 或 \(y \to x\)。会发现这样就能消掉一条边，构造出一个叶向树。
观察一下这个叶向树。称一个询问给出的 \(2(k + 1)\) 个点为特殊点，对于叶向树上的一个点，它能到达的充要条件是在祖先与后代中分别存在可以从 \(s\) 到达也可以到达 \(t\) 的特殊点，称这些特殊点为关键点。
由于 \(k\) 特别小，所以直接暴力找即可。统计答案考虑用虚树维护，在栈中维护一个点均为关键点的序列，就可以统计答案了。
代码挺难写。
其实还有更魔怔的做法用树剖和珂朵莉树维护这个东西。
AT_arc092_d
在机房电脑上。
CF1361E
这种题显然要先考虑如何判定一个点是否合法。会发现一个点合法当且仅当以这个点为根的 DFS 树上不存在横叉边与前向边。
考虑找到一个合法点后如何判定其它点是否合法。由于我们图上只存在返祖边，所以只需要考虑返祖边的影响。
对于一条返祖边 \((u, v)\) 相当于覆盖了 \(v \to u\) 路径上的所有点（不包括 \(v\)），对于一个点 \(x\)，如果被超过一条返祖边覆盖，则一定不合法。
于是考虑树上差分即可。现在问题是怎么找出一个合法点。
由于题目中说明存在 \(80 \%\) 的有趣城市，于是我们直接随机化找点就是对的。如果没找到说明不符合条件，输出 \(-1\)。