首页 > 其他 > 详细

bzoj 1051 强连通分量

时间:2015-02-25 23:34:21      阅读:370      评论:0      收藏:0      [点我收藏+]

 

反建图,计算强连通分量,将每个分量看成一个点,缩点后的图是一个DAG,如果是一棵树,则根代表的连通分量的大小就是答案,否则答案为0.

 

收获:

  图的东西如果不好解决,可以尝试缩点(有向图将每个强连通分量看成一个点,无向图将每个双连通分量看成一个点),缩点之后图就变成DAG或无向无环连通图,原本没有的一些性质就会在这是凸显出来,而且缩点的复杂度很低。

bzoj 1051 强连通分量

原文:http://www.cnblogs.com/idy002/p/4300347.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!