传递闭包

时间复杂度：

  • O(n^3)

算法解释：若 a->b, b->c 则 a->c，将所有的间接到的点化为直接到，如此称为传递闭包

算法思路

  • 直接Floyd算法
  • 更新距离的函数变一下即可

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void floyd()
{
    memcpy(d, g, sizeof d);
    
    for (int k = 0; k < n; k ++ )
        for (int i = 0; i < n; i ++ )
            for (int j = 0; j < n; j ++ )
                d[i][j] |= d[i][k] & d[k][j];
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ )
    {
        int a, b;
        cin >> a >> b;
        g[a][b] = 1;
    }

    return 0;
}