[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 }