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

题目描述

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

如图

[JSOI2010]连通数

顶点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();//计算有多少个1
24     cout<<ans<<endl;
25     return 0;
26 }
声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。