P4171 [JSOI2010] 满汉全席

将问题简化为两排节点，每列选一个，满足 \(m\) 个条件。目前到这里没问题。

我们注意到：如果选择一个“满”节点，而对应的“汉”又是一个条件的一半，那么一定要选这个条件的另一半，否则就无法满足该条件。

如图红圈表示一个条件。对于它，我们把绿勾节点和橙勾节点建一条有向边，表示如果绿勾节点被选择，橙勾节点必须被选择。跑 tarjan，看同一列的两个点是否相互可达（如果上面节点被选择，下面节点也需要被选择，矛盾；如果下面节点被选择，上面节点也需要被选择，矛盾；所以必须是有向图的相互可达），也就是看两点是否在同一强连通分量中。