有N个变量,每个变量都能取T或F,需要满足M个条件: or
要给每个变量赋值,满足所有条件.
构造有向图G,每个拆成两个点2i和2i+1, 分别表示取T或者F. 每个变量选其中的一个进行标记,标记了节点2i表示,标记2i+1表示.
对于每个条件,如 or ,可以从表示点i为F的节点到表示点j为F的节点连一条边,表示如果点i为F,那么点j一定是F. 同时,还要从表示点j为T的点向表示点i为T的点连一条边.