传递闭包

传递闭包是一种关于连通性的算法，她可以在 N^3的复杂度内求出所有点的所能到达的点集。

伪代码：

For 每个节点i Do 
    For 每个节点j Do 
    If j能到i Then 
        For 每个节点k Do 
        a[j,k] := a[j,k] Or ( a[j,i] And a[ i,k] )

复杂度看起来很不友好，但经过bitset的一番调教后其变为了N^2;
放一道裸题：P4306 [JSOI2010]连通数
bitset的具体用法见大佬blog ：https://www.cnblogs.com/RabbitHu/p/bitset.html
代码：

#include <bits/stdc++.h>
using namespace std;
const int MXN = 2010;
int n;
char s[MXN];
bitset<MXN> a[MXN];
int main() {
    scanf("%d",&n);
    for (int i = 0; i < n; i++) {
        scanf("%s",s);
        for (int j = 0; j < n; j++) a[i][j] = s[j] - ‘0‘;
        a[i][i] = 1;
    }
    for (int k = 0; k < n; k++)
        for (int i = 0; i < n; i++)
            if (a[i][k]) a[i] |= a[k]; //传递闭包 
    int ans = 0;
    for (int i = 0; i < n; i++) ans += a[i].count();
    printf("%dn",ans);
    return 0;
}