Beyond the Void

这道题难在对图的深入分析。如果一个人能够看见两个不同的人，那么这两个人所戴的面具种类一定相同，同样，如果一个人能被两个人看见，这两个人所戴 的面具种类也一定相同。把每个人当作图中的一个顶点，a能看见b，则连接(a,b)一条有向边。我们把能够推断出的带相同面具的人成为一个类。

显然图中可能会有多个连通分量，对于某个连通分量，如果把边的方向去掉，该连通分量中存在一个无向环，则称该连通分量为环结构，否则成为 树结构。可以发现，一个环结构的连通分量，逐步把一个类的所有顶点收缩为一个顶点，最终一定会剩下一个有向环，而一个树结构的连通分量也会变成一个单向的 有向树。一个环结构的连通分量，最终有向环上顶点个数，就是该连通分量的最大类数，而且，最大类数的所有约数也都可以满足该连通分量的类数。而树结构连通 分量，有向树中的最长路径，就是该连通分量的最大类数。

显然环结构是关键的，如果同时存在树结构和环结构的连通分量，树结构可以忽略。如果存在两个（或多个）环结构连通分量，它们类数的最大公约数可以就是满足这两个连通分量的最大类数，它们类数的最大公约数的大于等于3的最小公约数就是满足这两个连通分量的最小类数。

关键问题就是求一个环结构连通分量的等价环的长度。收缩等位顶点的方法不便于编写，我们可以用一遍DFS的方法。对于一个连通分量，从一个 顶点开始DFS，有向边可以双向走，第一个顶点标号1。遇到正向的边，标号加1，遇到反向的边，标号减1。遇到已经访问过的点，则说明找到了一个等价环， 长度为该点应该被标的标号减去已有的标号的差的绝对值，标号不改变然后返回继续DFS。这样以O(N+M)的时间求出所有等价环长度，算出最大和最小公约 数即可。

Read the rest of this entry »

这是合并等价类问题，由于每个未知量有多位，每位对应0或1，我们先把字母串按照展开拆开。例如样例可以展开成

1,b1,b2,a1,a2,a3,a4,d1,d2,d3,d4, 1
a1,a2,a3,a4,c1,c2,c3,c4,b1,b2,e1,e2

对于上述对应关系，进一步抽象成5个集合，每个元素属于唯一的一个集合，每个集合对应0或1。

{1,a1,a4,c3,e2}
{b1,a2,c1,d2}
{b2,a3,c2,d3}
{d1,c4}
{d4,e1}

除了第一个集合一定为1以外，其余四个集合都有两种可能的解，根据乘法原理，解的总数为2^4=16。

对于这道题而言，可能会无解。无解的情况之一是两个串展开后长度不相等，这样就会有一些没有对应关系，所以无解。另一种情况就是两个已知量1和0属于同一个集合，这显然是有悖于事实的，也是无解。

求等价类集合的方法可以用并查集，也可以按照关系构图，求无向图连通分量的个数。两种方法的时间复杂度都可以近似认为是O(N)的。

下面是我的代码，用了并查集。

Read the rest of this entry »