逻辑推导问题
同时成立问题
同时成立问题一般是给若干个逻辑变量，且这些变量之间存在推导关系，问某个变量且运算后是否还可能为真。
题目1：给定$n$个火鸡，之后来了$m$个人，第$i$个人会等概率选择$x_i$和$y_i$两只火鸡中任意一条活着的火鸡，并吃掉它（如果两条都已经被吃了，就什么事情都不做）。接下来给出$q$个请求，每个请求给定火鸡的一个子集$S$，询问子集中所有火鸡是否可能在过程结束后同时存活。其中$n\leq 500,m\leq 10^5,q\leq 10^5$。
首先对于第$i$个人，我们记其操作为$(x_i,y_i,i)$。在图论上看就是在时间$i$在$x_i$和$y_i$之间加入一条双向边。
这等价于给定$n$个变量$t_1,\ldots,t_n$，其中$t_i$记作火鸡$i$的死亡时间。现在对于任意一个人$(u,v,i)$。其要求$t_u=i\lor t_v=i\lor \max(t_u,t_v)<i$，即一只火鸡的时间时间恰好为$i$，或两只火鸡都在时间$i$之前被吃。
现在我们希望$S$中的火鸡最后都存活，则可以令$i\in S$，将$t_i$设置为无穷，而其余变量不设置。
之后我们可以从$S$的所有火鸡作为根进行DFS。假设现在的根为$root$。我们遍历所有出现时间在$root$被吃之前的边，将另外一端的顶点的死亡时间设置为边的出现时间（由于$t_u>i$，因此要使得边的条件满足，必须有$t_v=i$）。如果一个火鸡被两次设置死亡时间，两次设置的边的出现时间一定不同，因此这里产生了悖论，即火鸡不可能同时存活，否则我们可以将所有未被设置死亡时间的火鸡的死亡时间全部设置为$0$，即一开始就全部死亡。
先证明上面的算法是正确的。在报告出现悖论的情况，一定是不能同时存活的，这点不用证明（因为是直接推导出的结果）。下面证明在没有报告悖论的时候，确实是能同时存活的。可以发现边$(u,v,i)$（也就是条件）分为三类，：第一类边是$u,v$都被设置了死亡时间，如果边的时间比两个端点的死亡时间大，则没问题，否则如果边的时间比一个端点大，则在处理这个端点的时候会处理这条边，因此另外一个端点的死亡时间恰好是边的出现时间。因此第一类边的条件是满足的。第二类边是只有一个端点被设置了死亡时间。那么这条边的时间一定大于等于这个端点的死亡时间，而另外一个端点的死亡时间为0，因此条件一定成立。同理对于第三类边：两个端点都被设置了死亡时间，由于$\max(t_u,t_v)<i$，因此条件依旧成立。
虽然算法是正确的，但是时间复杂度又如何呢。简单估算应该是$O(qn(n+m))$。注意到每个顶点只需要处理一次（因为最多被赋值一次），因此时间复杂度可以降低到$O(q(n+m))$。我们还可以加上一些剪枝，在发现悖论的情况下直接跳出，于是这样可以保证最多只有$O(n)$条边被处理（每处理一条边就会对某个变量$t_i$进行赋值，且不允许重复赋值），因此时间复杂度为$O(q(n+m))=O(qn)$。