Algoritmia - Modificación BFS/DFS

Hola!

Tengo que diseñar un algoritmo a partir del BFS o DFS que haga lo siguiente:

Partiendo de un vértice s, comprobar si existe como mucho un camino simple (no se repiten vértices en el camino) de s a cualquier otro vértice del grafo. El algoritmo tiene que ser O(|V|+|E|).

Y después a partir del anterior algoritmo, modificarlo para que compruebe lo mismo (que haya como mucho 1 camino simple) entre u y v. Este algoritmo debe ser O(|V||E|).

Muchísimas gracias de antemano! Espero que me podáis ayudar! :)

Lo primero lo haces efectuando un simple bfs sobre el grafo y todos los vértices que entren en la cola los marcas como vértices a los cuales existe un camino simple. (esto también lo puedes hacer con un dfs).
Lo segundo se resuelve de la siguiente forma:
haces una matriz de |V|x|V| y luego por cada vértice aplicas el primer algoritmo. El resultado lo pones en la fila correspondiente al vértice que estes analizando. Finalmente en la matriz quedara en la posición u,v si existe un camino simple entre u y v. Lo interesante aquí es el costo temporal. Es O(|V|+|E|) pues tenemos O(|V|*(V|+|E|))=O(|V|**2+|V|*|E|)=O(max(|V|**2,|V|*|E|))=O(|V|*|E|)