CareerCup

I suggest to use union find disjoints sets and run two times...then when i would like to know if 2 nodes are connected just access to pset and check if have same numbers.... fo example, i have this graph:
1->2->3
4->5
UFDS:
first time
index: 1 2 3 4 5
element(pset): 2 2 3 5 5

second time
index: 1 2 3 4 5
element(pset): 3 3 3 5 5

3 and 4 are connected ? 3 and 5 are equal ? No.
1 and 2 are connected ? 3 and 3 are equal ? Yes.

Can't you run DFS/BFS once and store the connectivity information as an index, say?

Next time the connectivity query will be a constant time operation of just checking the corresponding indices for equality.

If two vertexes are connected in Directed graph, it means that they belongs to the same Strongly connected component. You can find all SCC by DFS in O(n).
Traverse graph by dfs and save enter in(v) and exit time out(v) for each of them. Then invert all edges(actually transpose adjecency matrix) and make dfs again, but when you in vertex v, you should to choose first those vertex that has maximum out time. So all distinct trees of dfs will be strongly connected components.
So you have preprocess the graph, so then all you need it is just to check whether both vertexes belong to the same SCC, it can be done in O(1).

1->2->3 
4->5 
UFDS: 
first time 
index: 1 2 3 4 5 
element(pset): 2 2 3 5 5 

second time 
index: 1 2 3 4 5 
element(pset): 3 3 3 5 5