[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();//计算有多少个1
24     cout<<ans<<endl;
25     return 0;
26 }