CF999E. Reachability from the Capital (2000)#

链接：题目链接｜提交记录

题意：给定 $n$ 个点 $m$ 条边的有向图和起点 S。求最少添加多少条边，使得可以从 S 出发到所有点。

考虑点 x 无法从起点 S 走到，那么添加边从 S 连向 x 溯源最早的点。如果是一个环，那么根据连通性缩点，S 连向这个集合任意点即可。

最后答案是求 scc 并缩点转换成 DAG 后，入度为 0 且不包含起点的点的个数。

时间复杂度：$O(N + M)$。

CF1131D. Gourmet choice (2000)#

链接：题目链接｜提交记录

题意：给定两个长度为 $N$ 和 $M$ 的数组 $A$ 和数组 $B$ 元素间的两两关系（包含 >, <, =）。为每个元素分配正整数，使得满足所有关系且打分的最大值最小。

对于 $x = y$，两个值必须相等，用 dsu 合并成一个点。考虑建图，如果 $x > y$，那么从 $y$ 所在连通块向 $x$ 所在连通块连一条有向边。$x < y$ 同理。

把入度为 $0$ 的点设为 $1$，进行拓扑排序，转移时更新相邻节点的值 $ans[y] = \max(ans[y], ans[x] + 1)$。保证每个点取到满足限制的最小正整数。

若拓扑排序无法遍历所有点，则无解。

时间复杂度：$O(NM)$。

1213F. Unstable String Sort (2100)#

链接：题目链接｜提交记录

题意：给定两个长度为 $n$ 的排列 $p$ 和 $q$，一个正整数 $k$。要求构造出一个由小写字母构成的长为 $n$ 的字符串 $s$，使得对于所有 $i \in [1, n - 1]$，均满足 $s[p[i]] \le s[p[i + 1]]$ 且 $s[q[i]] \le s[q[i + 1]]$。且 $s$ 中至少包含 $k$ 种不同的小写字母。

考虑建图，如果 $s[x] \le s[y]$，那么从 $x$ 向 $y$ 连一条有向边。显然，若图中存在环，则环中所有字符必须相等。因此通过 tarjan 求 scc 并缩点。

缩点后得到 DAG，若 scc 的总数小于 $k$，则意味最终能分配的不同字符种类数将小于 $k$，无解。否则按照拓扑排序分配字符即可。

时间复杂度：$O(N)$。

1547G. How Many Paths? (2100)#

链接：题目链接｜提交记录

题意：给定 $n$ 个点 $m$ 条边的有向图（可能包含自环）。求顶点 $1$ 到每个点的路径条数，用 $0, 1, 2, -1$ 分别表示 $0$ 条、$1$ 条，有限多条和无限多条。

考虑路径为无限多条的充要条件：该点可以被一个从 $1$ 可达的环（或自环）到达。

求 scc 并缩点，若某个从 $1$ 可达的 scc 大小 $>1$ 或包含自环，则其内部及由此能到达的点为 $-1$。

对于剩余的点，在缩点后的 DAG 上按拓扑序 dp 即可。

初始状态：$f[0] = 1$，其余 $f[x]=0$。

状态转移：若 $f[x] = -1$，$f[y] = -1$；否则，$f[y] = \min(2, f[y] + f[x])$。

时间复杂度：$O(N+M)$。

650C. Table Compression (2200)#

链接：题目链接｜提交记录

题意：给定一个 $n \times m$ 的矩阵 $a$。要求构造一个矩阵 $a'$，使得 $a'$ 的每行、每列元素的相对大小关系（$<, =$） 与 $a$ 对应行、列完全一致，且 $a'$ 中的最大值尽可能小。

比较直观的做法是，建图后拓扑排序：将相同的点利用 dsu 缩点，然后根据严格小于的关系建有向边。

可以贪心简化建图和拓扑排序过程，将矩阵中所有元素按数值从小到大排序顺次确定，每个位置的新值，实际上只取决于它所在行和所在列目前已经确定的最大值，即新值等于所在行列历史最大值 $+1$。

但当矩阵中出现多个数值相同的点时，如果它们处于同一行或同一列，题目要求它们的新值必须绝对相等，这种约束具有传递性。用 dsu 将这些点所在的行节点和列节点合并，用所在集合的共同最大值然后更新即可。

时间复杂度：$O(NM \log{(NM)})$。

22E. Scheme (2300)#

链接：题目链接｜提交记录

题意：给定 $n$ 个点 $n$ 条边的有向图，每个点的出度恰好为 $1$。求最少添加几条边使其变成强联通图，并给出构造方案。

每个点的出度均为 $1$，可以知道这是一个基环内向树森林，求 scc 缩点后每个联通块必然只有 $1$ 个汇点，至少 $1$ 个源点。

图变成 scc 的条件是：只有一个联通块，且不存在入度为 $0$ 或出度为 $0$ 的点。

因此，加边数量的下界是汇点总数和源点总数的最大值，由于是基环内向树森林，恰好等于源点个数总和。

考虑将 $i$ 个联通块的汇点建边连向第 $i + 1$ 个联通块的所有源点，满足下界。

特判原图已经是强连通图，此时不需要加边，答案是 $0$。

时间复杂度：$O(n)$。