AGC006F Blackout

按照套路，我们应该把行和列看成点，即有 $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$。