P7909 题解

aberter0x3f · 2021-10-19 19:41:50 · 题解

介绍一种使用 bitset 的做法。

我们可以对每一个点建一个 bitset，来代表从这个点出发能够到达的点，然后就简单了，二进制位上的 1 表示能到达，0 表示不能到达。最后依次输出这 n 个 bitset 即可。

具体过程，可以参考 floyd 算法。即枚举 i,j，如果 j 可以到达 i，那么点 i 能到的点肯定能被点 j 所达到。使用 bitset 的或运算即可轻松实现这个过程。

#define rep(i, f, t) for (int i = (f), ed##i = (t); i <= ed##i; ++i)
#define re(i, t) rep(i, 1, t)
bitset<N> a[N];
int n;
int main() {
  in(n);
  re(i, n) a[i][i] = 1;
  re(i, n) re(j, n) a[i][j] = in();
  re(k, n) re(i, n) if (a[i][k]) a[i] |= a[k];
  re(i, n) {
    re(j, n) out((int)a[i][j])(' ');
    out('\n');
  }
  return 0;
}