传递闭包

原理

见《进阶指南》第359页。

模板题

洛谷-P4306-连通数

#include <iostream>
using namespace std;

const int N = 2010;
int n, g[N][N];

int main () {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++ i)
        for (int j = 1; j <= n; ++ j)
            scanf("%1d", &g[i][j]);

    for (int i = 1; i <= n; ++ i) g[i][i] = 1;
    for (int k = 1; k <= n; ++ k)
        for (int i = 1; i <= n; ++ i)
            for (int j = 1; j <= n; ++ j)
                g[i][j] |= g[i][k] & g[k][j];
    
    int res = 0;
    for (int i = 1; i <= n; ++ i)
        for (int j = 1; j <= n; ++ j)
            res += g[i][j];
    printf("%d", res);
    return 0;
}