# Checking if there exists a 'source' vertex

In a directed graph $$G=(V,E)$$ we denote a vertex $$s\in V$$ to be a 'source' if there exists in $$G$$ a path from $$s$$ to all other vertices $$u \in V$$.

The problem asks for an efficient algorithm to return the 'source', in case there isnt any, return false.

I've been able to come up with a naive approach to his problem:

$$\forall v\in V$$:

Do $$DFS(v)$$, mark $$S_v$$ to be the set of vertices contained in DFS tree starting at $$v$$

if $$|S_v|=|V|$$, return $$v$$

After doing this for all $$v\in V$$, if we finished looping, return false.

This algorithm runs in $$O(|V|\cdot (|V|+|E|))$$ which is far from what I'm looking for, however I am unsure how to improve this.

EDIT:

Since we know a DAG has a vertex $$v$$ which $$degree_{in}(v)=0$$, we can use this fact to solve this problem:

I've come up with a new algorithm with a $$O(|V|+|E|)$$ runtime:

1. perform tarjan's algorithm to find SCC's and create the quotient graph $$G'$$.

(since the quotient is a DAG, we can apply the topological sort algorithm)

1. perform a topological sort on $$G'$$, mark $$v$$ to be the first node after sorting

2. perform $$BFS$$ on the first node after sorting.

3. if any of the paths from $$v$$ to a node in $$G'$$ is of length $$\infty$$ (which means there isnt a path from $$v$$ to said vertex), return that there is no source vertex.

4. return $$v$$

I'm not completely sure about choosing the first vertex after sorting, but it's the only thing that came to mind.

Are there any ways to improve this/simplify in a way that the proving stage would be simpler?