一个比较简单的图论问题，总算是填了这个小坑

Problem

有一些集合，每个集合中有且仅有两个元素，且不能同时选取两个元素，集合间的元素存在一定的选择关系，求解可行性及可行方案

Algorithm

其实这也不算是一个算法，就是一个很简单的图论模型，特别详细的过程可以看这里

把每个点拆成两种状态aa和a′a'，状态之间互相连形如如果选a则必须选b的有向边，通过tarjan求强连通分量来判断可行性

算法流程如下：

  • 连边

  • 跑tarjan

  • 判可行性：判断一个点的两种状态是否同属一个强连通分量

  • 输出方案：输出两种状态中较先被缩成强连通分量的那个状态即可

    这个本质是对强连通分量进行缩点，缩完后形成的树（或者说是DAG也行）上显然如果状态xx被选，那么xx的子树的所有状态都要选。于是对于同一个点的两种状态而言，肯定只能选深度较深的那种状态，这种状态显然在用tarjan缩点时会先被缩起来

Connection

关于连边，主要思想就一个：选了a必选b对应连边a→ba\rightarrow b和b′→a′b' \rightarrow a'（逆否命题，必须也要连），然后根据相应的逻辑关系进行连边

常见的逻辑关系有：

  • aa、bb不能同时选：选了aa就要选b′b'，选了bb就要选a′a'
  • aa、bb至少选一个：选了 就要选bb，选了 就要选aa
  • aa、bb必须同时选：选了aa就要选bb，选了bb就要选aa，选了a′a'就要选b′b'，选了b′b'就要选a′a'
  • aa、bb必须选一个：选了aa就要选b′b'，选了bb就要选a′a'，选了a′a'就要选bb，选了b′b'就要选aa
  • aa必须选：a′→aa'\rightarrow a
  • aa必须不选：a→a′a\rightarrow a'

Example

懒的放了