Is there a known algorithm which runs in close to linear time, which receives a k-partite directed graph and outputs all pairs (s,t) where s is a vertex in the 'first' part of the graph and t is a vertex in the 'k-th' part?

EDIT: I wasn't specific enough. The assumption is that there are only edges between G_i and G_{i+1} for each i. This would be clear at first sight from a picture, and I haven't found a way to express it succinctly in words (suggestions are welcome).

EDIT: all pairs (s,t) ... such that there is a path from s to t.