AGC006F Blackout

我们有一个 $N$ 行 $N$ 列的矩阵。第 $i$ 行第 $j$ 列的格子表示为 $(i,j)$。

开始时，有 $M$ 个格子是黑色，其他格子都是白色。特别地，开始时格子 $(a_1,b_1),(a_2,b_2),\cdots ,(a_M,b_M)$ 是黑色。

スヌケ君会按照以下的规则尽可能多的将白色格子涂成黑色：

• 对于整数 $1\le x,y,z\le N$，如果 $(x,y)$ 和 $(y,z)$ 都是黑色，那么就把 $(z,x)$ 涂黑。

请计算出当再也没有白色格子能被涂黑时，黑色格子的个数。

$1\le N,M\le {10}^5;1\le a_i,b_i\le N$。¹

题解

按照套路，我们应该把行和列看成点，即有 $1\sim N$ 个点，每个格子 $(x,y)$ 可以看成是 $x\to y$ 的一条有向边。如果存在边 $(x,y)$ 与边 $(y,z)$，就连边 $(z,x)$，询问最终有几条边。

我们将每个弱连通分量分开考虑。

我们考虑什么时候不能加边了，大概是这 $2$ 中情况：

1. 已经是完全图了，边数为 $n\times (n-1)$。
2. 图被划分为 $3$ 个集合（可以是空集）$A,B,C$，$A$ 的所有点向 $B$ 的所有点连边，$B$ 的所有点向 $C$ 连边，$C$ 的所有点向 $A$ 连边，边数为 $|A|\times |B|+|B|\times |C|+|C|\times |A|$。

我们发现一个点集如果会到情况 $2$，那就到情况 $2$，否则就是情况 $1$。

于是我们尝试划分集合，将弱连通块中每个点一遍 dfs 染色，如果染色成功，那就是情况 $2$，否则就是情况 $1$。