传递闭包

传递闭包

思路：

Warshall算法求传递闭包

1. 用原始二元关系\(R[i][j]\)给\(T[i][j]\)赋初值

2. 类似Floyd-Warshall算法，三层循环

   用外层k，更新 \(i->j\)

   这里的更新指的是：假如\(T[i][k]=1\)且\(T[k][j]=1\)，则\(T[i][j]\)应该被赋为1

   形象的说：i，j通过k“粘”了起来(i->k，k->j，去掉连接点k，i->j直接相连)

优点：

避免了使用\(t(R)=R∪R^2∪R^3∪...∪R^n\)，即\(M_t=M+M^2+M^3+...+M^n\)，时间复杂度较高的方法

int n,a[N][N],b[N][N];void warshall()
{for(int k=1;k<=n;++k){for(int i=1;i<=n;++i){for(int j=1;j<=n;++j){if(b[i][k]==1&&b[k][j]==1)b[i][j]=1;}}}
}int main()
{cin>>n;for(int i=1;i<=n;++i){for(int j=1;j<=n;++j){cin>>a[i][j];b[i][j]=a[i][j];}}warshall();for(int i=1;i<=n;++i){for(int j=1;j<=n;++j){cout<<b[i][j]<<" ";}cout<<"\n";}return 0;
}