一行有N个学生。我们想拍出最好的照片。当学生满意的人数最多时，照片被认为是最好的。如果是最好的朋友的邻居，学生就会感到满足。每个学生只有一个最好的朋友。你必须找到满意的学生的数量在最好的照片和不同的最好的照片的数量。
方法:
。
- 每个节点都在循环中。(每个节点都有一个传入边和一个传出边)。这里我们可以满足所有节点，除了一个(最左边的节点)。因此满足节点为N−1，不同的变量为N
-
，至少有一个入边可以满足一个节点。因此，很容易计算出满足的节点数。设数组B，其中B[i]是i的入边数，满足最大节点数的另一种方法是B的乘积。但是有一些"BAD"变体，满足所有循环节点。但我们可以很容易地减去"坏"变体。在循环节点的"BAD"变体中，我们确切地知道它们满足谁。所以不同的变体是:
B (K1) * B (K2)……B[Kn] - B[P1]*B[P2]....B[点]
其中K是组件中节点的数组(至少有一个传入边)，p是不在该组件循环中的节点的数组(至少有一个传入边)。
我不能理解坏变量的概念，为什么我们要减去它们。
请解释并能给我一些这类问题的有用链接
我宁愿再写一篇社论，也不愿去弄清楚那篇到底是怎么回事。
准备一个"最好的朋友"有向图，其中每个顶点是一个学生，每个学生到他最好的朋友有一条弧。提取这个图的弱连通分量。在每个组件中，我们可以满足除一个学生之外的所有学生，但前提是该组件中的学生连续站立。因此，我们可以计算出每个组件的可能性数量，将它们相乘，并乘以组件数量的排列数量(即组件数量的阶乘)。
对于给定的组件，有两种可能。第一种可能是，一个顶点完全没有弧，一个顶点恰好有两个弧，其余顶点有一个弧。以前的学生必须是最正确的，所以有一个有效的安排。第二种可能性是所有的顶点都有一个进弧。在这种情况下，有效排列的数量等于组件中的顶点数量(任意选择最右边的学生，然后绕循环一圈)。