题意:给定一个有向图,寻找一个点数最大集合,使得这个集合中的任意两个点
u,v, 都有u->v 或者 v->u 或者u<==>v
思路:首先将强连通分量通过tarjan算法求出来,然后进行缩点,也就是每一个缩点
所组成的图就是一个DAG图!令每一个点的权值就是这个缩点所包含节点(也就是对应的
强连通分量的节点数目),因为强连通分量的任意的两个节点都是相互可达的,那么这个
缩点要么选要么不选,问题就转换成了DAG图上的最长路径!
View Code
本文转自 小眼儿 博客园博客,原文链接:http://www.cnblogs.com/hujunzheng/p/4019695.html,如需转载请自行联系原作者