Description
Warning：本文只介绍传递闭包在 OI 中的简单应用。
传递闭包在 OI 中，一般用来处理图上点之间的连通性问题。它在图上体现在 原图上任意两个直接或者间接可达的点都连边。
在上图中，显然 \(\{1,2\}\{2,3\}\{1,3\}\) 均可达。在“传递闭包图”上如上三对点对都需要连边。
不难发现传递闭包可以通过 Floyd 算法求解。
Floyd 本质是枚举每个中转点 \(k\) ，对于 \(\forall i,j\) 。如果可以通过 \(k\) 中转可达，那就连边。
朴素 Floyd 算法是 \(O(n^3)\) 的，我们可以使用 bitset 优化。
这里给出 Floyd 算法求传递闭包模板：
Floyd 传递闭包
void floyd()
{
for(int k=1;k<=n;k++)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
f[i][j] |=(f[i][k]&&f[k][j]);
}
}
}
}
接下来会给出几个简单应用。
Practise 1
题目给定 \(m\) 组大小关系，需要求有几个点的顺序确定。
我们只需要将大小关系建图，然后求解传递闭包。最后判断在传递闭包图上该点到图上其他点是否均可达即可。
持续更新。
标签：闭包,连边,图上,笔记,传递,算法,Floyd From： https://www.cnblogs.com/SXqwq/p/18077382