UVAoj 11324 - The Largest Clique(tarjan + dp)

简介:

题意:给定一个有向图,寻找一个点数最大集合,使得这个集合中的任意两个点
u,v, 都有u->v 或者 v->u 或者u<==>v

思路:首先将强连通分量通过tarjan算法求出来,然后进行缩点,也就是每一个缩点
所组成的图就是一个DAG图!令每一个点的权值就是这个缩点所包含节点(也就是对应的
强连通分量的节点数目),因为强连通分量的任意的两个节点都是相互可达的,那么这个
缩点要么选要么不选,问题就转换成了DAG图上的最长路径!

  View Code









本文转自 小眼儿 博客园博客,原文链接:http://www.cnblogs.com/hujunzheng/p/4019695.html,如需转载请自行联系原作者
目录
相关文章
LeetCode 404. Sum of Left Leaves
计算给定二叉树的所有左叶子之和。
81 0
LeetCode 404. Sum of Left Leaves
CF1365D Solve The Maze (BFS)
CF1365D Solve The Maze (BFS)
84 0
CF1365D Solve The Maze (BFS)
codeforces1426——F. Number of Subsequences(DP)
codeforces1426——F. Number of Subsequences(DP)
105 0
CodeForces 377A-Maze(DFS找连通块)
CodeForces 377A-Maze(DFS找连通块)
CodeForces 377A-Maze(DFS找连通块)
HDOJ(HDU) 2136 Largest prime factor(素数筛选)
HDOJ(HDU) 2136 Largest prime factor(素数筛选)
108 0
LeetCode之Sum of Left Leaves
LeetCode之Sum of Left Leaves
92 0