[JSOI2010]连通数(连通函数)

传送地址：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 顶点 3 ...

推荐整理分享[JSOI2010]连通数(连通函数)，希望有所帮助，仅作参考，欢迎阅读内容。

文章相关热门搜索词:连通图代码,连通图生成树的个数,连通技术,连通图生成树的个数,连通图计数,连通图生成树的个数,连通性算法,连通区域数,内容如对您有帮助，希望把文章链接给更多的朋友！

传送地址：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代码：

1 #include <bits/stdc++.h> 2 using namespace std; 3 const int N=2e3+5; 4 bitset<N> B[N];//给每一个节点建立bitset 5 int main() 6 { 7 int n;cin>>n; 8 for(int i=1;i<=n;i++){ 9 string s;cin>>s;10 for(int j=1;j<=n;j++){11 if(s[j-1]=='1'||i==j) B[i][j]=1;12 //能到这个节点或者自己13 }14 }15 for(int i=1;i<=n;i++){16 for(int j=1;j<=n;j++){17 if(B[j].test(i)) B[j]|=B[i];18 //如果j可以到达i，则i可以到达的所有节点j都能到达19 //这里的“|”在此不在讲述20 }21 }22 int ans=0;23 for(int i=1;i<=n;i++) ans+=B[i].count();//计算有多少个124 cout<<ans<<endl;25 return 0;26 }