连通区域算法（[JSOI2010]连通数）

时间2025-07-10 00:24:30分类IT科技浏览4816

导读：传送地址：https://www.luogu.com.cn/problem/P4306...

传送地址：https://www.luogu.com.cn/problem/P4306

题目描述

度量一个有向图连通情况的一个指标是连通数，指图中可达顶点对个的个数。

如图

顶点11可达1, 2, 3, 4, 51,2,3,4,5

顶点22可达2, 3, 4, 52,3,4,5

顶点33可达3, 4, 53,4,5

顶点4, 54,5都只能到达自身。

所以这张图的连通数为1414。

给定一张图，请你求出它的连通数

题解

这题打了半天，发现用dfs或者bfs都是会TLE

于是就想采用另一种方法：bitset

这样我们就可以用0代表不能到达，1代表可以到达

最后对对可以到的的进行求和即可

另外，关于bitset的使用以及函数调用，请参考：https://cplusplus.com/reference/bitset/bitset/?kw=bitset

其他就不多赘述了。

AC代码：

声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。