Since this is a digraph couldn't you do a topological sort on it? The nodes without any incoming edges should appear in either end, depending on sort order afaik.