AGC006F

Link

这题我大概一年前就做过，现在心情很糟。

直接说现在的心路历程。

看反了 \((x,y),(y,z) \rightarrow (z,w)\) 中的 \((z,w)\)。
受到一个cf题的影响，拼命想并查集，做成了二分图，没什么进展（因为没有联通性）。
看题解，得知应该看成有向图，用边的方向表示。
又看错题意回到了 1，认为这个和 noi day1 t3 很像。
不忍心又看了题解，接下来的做法是 expected solution (with my thought)。
建出有向图，对于其中任意一个点 \(x\) ，按出入边分类，这样并不能成功划分，因为存在向他方向有边，又向别的地方有边的点，如图所示。

就是图中的蓝点向外连的点，向红点连的点。以现在的标准并不能很好分类。

但可以发现他们共同的性质是 \(\text{blue} \rightarrow \text{u} \rightarrow \text{red}\rightarrow \text{blue}\cdots\text{and so on}\)。

也就是他们有着和 \(x\) 一样的性质，那就把他们分到与 \(x\) 一组。
这样可以把一个图分成三类点，很好计数。当然现在我们考虑的都是平凡的图，即没有重(chong)边（无向重(chong)边），无自环的图。
当然如果存在一个重边/自环，也挺好考虑的。

首先你发现重边自环等价，\(\text{u}\rightarrow \text{u}\ \ + \ \ \text{u} \rightarrow \text{v}=\text{v}\rightarrow \text{u}\) 反之亦然。

这个东西就像病毒一样，只要一个有了，与他联通的点就全会有。

而一个所有边都是重边和自环的子图，那么显然是个无向完全图，也可以计数。