Divide By Sixty Four

One bitset row per vertex: the inner loop becomes a single word-parallel OR, giving $O(n^3/w)$ with $w = 8$, about $1.0 \cdot 10^9$ word operations.

One bitset row per vertex: the inner loop becomes a single word-parallel OR, giving $O(n^3/w)$ with $w = 64$, about $1.3 \cdot 10^8$ word operations.

One char row per vertex: the inner loop becomes a single byte compare, giving $O(n^3)$ with the whole matrix in cache, about $8 \cdot 10^9$ byte operations.

One Kosaraju condensation per graph: the inner loop becomes a single DAG traversal, giving $O(n + m)$ with $w = 64$, about $4 \cdot 10^6$ edge operations.