题解：Strong Connectivity Strikes Back

题目理解

我们有一个有向图，已知原始图的强连通分量（SCC）划分。Bob可以擦除一些边的方向（即这些边变成无向边），要求：根据剩余有向边和原始SCC划分，能够唯一确定被擦除边的方向，且恢复后SCC划分不变。

目标是：找到最多能擦除多少条边，以及达到这个最大值的方案数（模$10^9+7$）。

---

核心思想

将问题分解为三部分：

1. SCC之间的边（缩点后DAG上的边）
2. SCC内部的边（同一SCC内的边）
3. 组合起来得到最终答案

---

关键观察

1. SCC之间的边

设缩点后有两个SCC：$C_i$和$C_j$（$i \neq j$），它们之间有若干条有向边（方向相同，因为若双向都有则它们应属于同一SCC）。

• 如果从$C_i$到$C_j$有$k$条边，且存在从$C_j$到$C_i$的路径（在原DAG上），那么这些边中最多只能保留1条有向边，其余$k-1$条可以擦除方向。因为如果全部擦除，可能产生歧义。
• 如果不存在从$C_j$到$C_i$的路径，则这些边全部可以擦除方向（因为方向必须是从$C_i$到$C_j$，否则SCC会合并）。

贡献计算：

• 可擦除边数：若存在反向路径则$k-1$，否则$k$
• 方案数：若存在反向路径则乘以$k$（选择保留哪一条），否则乘以$1$（全部擦除）

2. SCC内部的边

对于一个大小为$s$的SCC，考虑其内部的边。我们需要分析哪些边可以擦除方向而不破坏SCC的唯一恢复性。

关键结论：

• 如果擦除某些边的方向后，得到的无向边集合使得SCC仍然保持强连通，且方向可以唯一确定，那么这些边可以擦除。
• 更具体地，对于SCC内部的一个边集，如果擦除后得到的“无向图”中，任意定向都能得到原SCC结构，则该边集可行。

做法： 对于SCC内的每条边$e=(u,v)$，尝试将其反向（即暂时删除原方向，添加反向边），然后计算新图的SCC情况。如果：

• 新图的SCC个数与原SCC个数相同，且SCC划分完全一致，则说明这条边可以擦除方向（因为它的方向由其他边唯一确定）。

实际上，通过哈希来识别：对于每条边$e$，计算去掉$e$并添加反向边后的SCC划分的哈希值。如果多个边得到相同的哈希值，说明它们可以互换方向而不改变SCC结构。

贡献计算：

• 将SCC内的边分组，每组内边可以互相替换（擦除后可以唯一恢复）
• 设一组有$b$条边，若它们能形成大小为$a$的SCC结构：
  • 若$a=1$：这条边不影响连通性，不能擦除（擦除后方向无法确定）
  • 否则：可以擦除$b-1$条边，方案数为$b$

---

算法步骤

第一步：求原图的SCC

使用Tarjan算法，得到每个顶点所属的SCC编号（$col[i]$），以及SCC总数$tot$。

第二步：处理SCC之间的边

1. 建立缩点后的DAG
2. 对于每对SCC $(i,j)$，统计从$i$到$j$的边数$fl[i][j]$
3. 判断是否存在从$j$到$i$的路径（在DAG上），使用DFS
4. 根据判断结果累加贡献：
   • 若存在反向路径：可擦除$fl[i][j]-1$条，方案数乘$fl[i][j]$
   • 否则：可擦除$fl[i][j]$条，方案数不变

第三步：处理SCC内部的边

1. 对每个SCC单独处理
2. 对于SCC内的每条边$e=(u,v)$：
   • 临时删除$e$，添加反向边$(v,u)$
   • 计算新图在该SCC内的SCC个数和哈希值
   • 记录$(SCC个数, 哈希值)$
3. 将得到相同哈希值的边归为一组
4. 对于每组：
   • 若SCC个数$=1$：不能擦除（贡献$0$）
   • 若SCC个数$=$组大小：可擦除$b-1$条，方案数乘$b$
   • 否则：可擦除$b$条，方案数乘$1$

第四步：输出答案

• $ans1$：最大可擦除边数
• $ans2$：方案数（模$10^9+7$）

---

时间复杂度

• Tarjan求SCC：$O(n+m)$
• 处理SCC之间的边：$O(tot^2 + m)$
• 处理SCC内部的边：$O(\sum_{scc} (m_{scc} \cdot (n_{scc} + m_{scc})))$
• 总复杂度：$O(nm)$，对于$n,m \le 2000$可接受

---

示例验证

以题目样例为例：

• 边$(1,5)$：在SCC内，擦除后方向唯一
• 边$(3,4)$和$(4,2)$：在SCC内，属于同一组，可擦除其中一条
• 其他边：不能擦除或贡献已计入

最终得到$ans1=3$，$ans2=3$。

---

模数处理

方案数对$10^9+7$取模，使用long long和取模运算即可。

---

总结

本题的核心是将问题分解为SCC间和SCC内两部分，利用SCC的唯一性和图的拓扑结构，通过分析边的可替换性来确定最大可擦除边数和方案数。标程使用哈希来高效判断边的等价性，是处理此类问题的经典技巧。