单侧连通图的可达矩阵

单侧连通图是指在一个无向图中，对于任意两个顶点u和v，如果存在从u到v的路径，那么这个路径只能沿着边的方向前进，即不能逆向。在这样的图中，我们可以定义一个可达矩阵，也称为前驱矩阵或拓扑排序矩阵。

可达矩阵是一个二维数组，通常用M[i][j]表示节点i是否可以通过边直接到达节点j。具体来说：

- 如果存在一条从节点i到节点j的路径，则M[i][j]=1；
- 否则，如果不存在这样的路径（包括i和j相同的情况），则M[i][j]=0。

构建可达矩阵的过程通常是从源节点开始，逐层遍历图，更新矩阵。初始时，源节点对所有其他节点的可达值为1，然后根据边的关系逐步扩散可达信息。当遇到没有出度的节点（即孤立节点）时，它们已经是最后一层，不会影响后续节点的可达状态。

值得注意的是，单侧连通图保证了整个过程能够完成，因为不存在环路阻碍可达性检查。而且，可达矩阵是对图结构的一种简洁表示，可以用于解决一些图算法问题，比如寻找最短路径等。