Ly,

The algorithm for the transitive closure is fine. It's a typical Floyd-Warshall algorithm

// Make a random graph

let makegraph = fun n -> Array.init n (fun _ -> Array.init n (fun _ -> Random.int(2)))

// Compute transitive closure (in place)

let transitiveClosure = fun matrix ->

let n = Array.length matrix in

for k = 0 to n - 1 do

for i = 0 to n - 1 do

for j = 0 to n - 1 do

matrix.(i).(j) <- max matrix.(i).(j) (min matrix.(i).(k) matrix.(k).(j))

done;

done

I guess that by "equivalence class" you mean strongly connected components.

There are linear algorithm (Tarjan, Gabow) that are variants of DFS (depht first search) with bookkeeping http://en.wikipedia.org/wiki/Strongly_connected_component

You can compute the strongly connected components directly on the transitive closure. Notice you don't need to transpose it explicitely