Calculate reachability for every vertex from adjacency list

Given an adjacency list Map<Vertex, Set<Vertex>> for a DAG, I want to calculate the reachability of every vertex (i.e. if there there is path from u to v).

static Map<Vertex, Set<Vertex>> reachability(Map<Vertex, Set<Vertex>> adjList) {}

I know it is possible using Floyd-Warshall in O(V^3)

// Convert adjList to adjacency matrix mat
void reachability(boolean mat[][]) {
  final int N = mat.length;
  for (int k = 0; k < N; k++)
    for (int i = 0; i < N; i++)
      for (int j = 0; j < N; j++)
        mat[i][j] |= mat[i][k] && mat[k][j];
}

But I have a sparse graph (and an adjacency list), so what is the fastest way to do this?

Here is a simple O(|V||E|) solution in Scala (basically, for each vertex, do a DFS):

type AdjList[A] = Map[A, Set[A]]

def transitiveClosure[A](adjList: AdjList[A]): AdjList[A]  = {
  def dfs(seen: Set[A])(u: A): Set[A] = {
    require(!seen(u), s"Cycle detected with $u in it")
    (adjList(u) filterNot seen flatMap dfs(seen + u)) + u
  }
  adjList.keys map {u =>
    u -> dfs(Set.empty)(u)  
  } toMap
}

Executable version here: http://scalafiddle.net/console/4f1730a9b124eea813b992edebc06840