Weakly connected graph test What is the right algorithm for testing whether the graph is "weakly connected"?
The theory says:

Oriented graph $G=(V,E)$ is weakly connected graph if and only if for every two vertices $u,v \in V$ exists a directed path from $u$ to $v$ or directed path from $v$ to $u$.

 A: The best way to go about this is to perform some sort of either depth first or breadth-first search through the graph: for example, the depth first search would look something like this in pseudocode (y in the code is a "neighbor" of x if there exists an edge from x to y or from y to x)
start at random vertex x
initialize an empty stack
repeat:
    mark x as visited
    push x onto the stack
    if x has an unvisited neighbor y:
        x = y
    else:
        y = stack.pop()
untill the stack is empty

If the search concludes after visiting all vertices, then the graph is weakly connected. Otherwise, all visited vertices form a weakly connected component.
A: On the definition:
Your definition of weakly connected graph is:

  
*
  
*Directed graph $G=(V,E)$ is weakly connected graph if and only if for every two vertices $u,v∈V$ there exists a directed path from $u$ to $v$ or directed path from $v$ to $u$.
  

There is another definition of weakly connected graph, that is


  
*Directed graph $G=(V,E)$ is weakly connected if and only if it is connected as an undirected graph.
  

Please note that this definitions are not equivalent, in particular consider the following graph $G$ with $E(G) = \{(1,0),(1,2)\}$, that is,
$$0 \gets 1 \to 2$$
which does not have any directed path $0 \to^* 2$ nor $2 \to^* 0$. It means that it is not weakly connected according to the first definition, but it is according to the second.
Solution using the second definition:
Checking if a graph is weakly connected according to the second definition is easy: just run a DFS ignoring edge directions and test if you have visited all the vertices.
Solution using the first definition:
On the other hand, the case of the first definition is more tricky.
To put it in different words, it means that there are no incomparable elements in the transitive closure of the graph. The transitive closure might take some time to calculate, but we don't have to. Such elements can easily be spotted using the DAG of strongly connected components.
To check whether a graph is weakly connected according to the first definition you should check if the DAG of strongly connected components is a path (possibly of length zero).
I hope this helps $\ddot\smile$
