给一个有向无环图，如果一个点被选，所有它能走到的点必选。并给一些不能同时选的矛盾关系。求最多选的点数
【给一个有向无环图，如果一个点被选，所有它能走到的点必选。并给一些不能同时选的矛盾关系。求最多选的点数】 忽视掉第一个限定，只看第二个，这东西叫最大点独立集，是NPC。
所以就算第一个限定是个树形图也没用，做不了的。
■网友
要满足第二个条件就已经是npc问题了，如果假设P不等于NP的话，是没有多项式算法的。
■网友
independent set可以归约到这个问题 就一堆离散的点就已经是independent set了 因此肯定没有多项式的算法
■网友
我的想法是类似于分解强连通分量的做法，先bfs给点标号并统计点数量，然后权衡取哪些点时就是有限制的背包问题了，可以用几个set来维护与当前标号不能同时选的标号有哪些，做DP时就在set中找一下
推荐阅读
- 同比■同比增长7.1%！2021年的第一个节你花了多少钱？
- “他是我第一个会说普通话的老师”：一对师生折射青海山村蝶变
- 有必要重新开个C店吗
- 大学再有三个月就结束了，没学到知识，参加一个软件测试培训机构好吗
- 汽车|长安UNI-K又将开创一个新的"引力"纪元？
- 神话|武汉传奇父亲：一个平行班孩子创造的高考神话（感动上万家长）
- 王者荣耀李白能不能出肉
- 直播会成为品牌传播的另一个途径么有哪些可行的方法感觉有戏又没头绪好捉急。
- 怎样成为一名合格的Python程序员?
- 知乎有没有必要增加一个特别关注功能