BZOJ 2208 [Jsoi2010] 连通数

发布于 2017-06-12  154 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=2208

题意:给出一个有向图的邻接矩阵,求有多少组点对可以互相到达。


练习 bitset 的时候发现了这题...

bitset 优化传递闭包即可,\(O(n^3/32)\),由于数据水,可以卡过 (貌似并不慢)

正解是 tarjan 缩点后传递闭包,思想和实现都不困难,先不写了 (颓

 


一个非常弱的准退役OIER