洛谷P4306 [JSOI2010]连通数 题解 传递闭包/bitset

题目链接：https://www.luogu.com.cn/problem/P4306

传递闭包 bitset 模板题。

需要注意的是 \(i = j\) 时需将 \(g_{i,i}\) 标记为 \(1\) 。

示例程序：

#include 
using namespace std;
const int maxn = 2020;
int n, ans;
char s[maxn];
bitset g[maxn];

int main() {
    cin >> n;
    for (int i = 0; i < n; i ++) {
        cin >> s;
        for (int j = 0; j < n; j ++)
            if (i == j || s[j] == '1') g[i][j] = 1;
    }
    for (int i = 0; i < n; i ++)
        for (int j = 0; j < n; j ++)
            if (g[j][i])
                g[j] |= g[i];
    for (int i = 0; i < n; i ++)
        ans += g[i].count();
    cout << ans << endl;
    return 0;
}