题意
我们有 $n$ 个点和 $n$ 个边,其中第 $i$ 条边连接至 $a_i$ 点。每条边需要指定一个方向。求问,有多少种方案使图中不出现环。
思路
我们可以发现,每个点的度至少为一,那么我们便可以得出以下的结论。
假如我们一共 $k$ 个连通图,那么我们这 $k$ 个连通图中边的数量一定等于点的数量。
如果边的数量等于点的数量的话,我们的图便是一个基环树,假若我们的图如下所示有多个基环树。
我们不难发现基环树可以拆分为两个部分
- 以紫色为边的环
- 以环的点为根的树
对于所有的树,无论我们怎么算都无法将其变为环图,因此我们只需要统计树中边的个数 $k$ 即可算出这部分的答案 $2^k$
对于所有的环,我们只有两种方案(都朝向一个地方)让他们成为环,因此我们需要统计环的长度 $s$ 就可以得到这个环所带来的影响 $2^s - 2$。
那么我们的答案最终就是 $2^k\prod 2^s - 2$