CareerCup

without any precomputation not possible....
With precomputation use hashing to find if a path exists between two pairs.

Directed acyclic graph is equivalent to strictly partial order sets.
This problem can be solved by pre-construct a Hasse diagram for divisibility.
Ex.

-----------------90 (Exit)
                /|\
               / | \
             6  10  9
             \  /\  /
              \/  \/
              /\  /\ 
             /   3  \
            2    |    5
             \   |  /
              \  | /
                \|/
                 1(Entrance)

After precompute this hasse diagram, for any given start point and end point, we just need to find the corresponding value of them, and check whether the end point value is divided by the start point value.

Do a DFS on the graph until all nodes are visited so you end up visiting each node only once.

If you process each vertex after all of its edges have been visited, you can build up a list of endpoints for each node.

Below assumes a DFS function that calls processLate after all edges have been visited for a node.

void processLate(Vertex v)
{
  for (Vertex n : v.edges)
  {
    if (n.edges.size() == 0) // check for neighbor with no edges (endpoint)
    {
      v.ep.add(n); // add neighbor to list of endpoints for this vertex
    }
    else
    {
      v.ep.add(n.ep); // neighbor not an end point, but already processed so grab it's endpoints
    }
  }
}

With this precomputing, you only need to check if the endpoint is in the list of a given starting node.

Hi all, I am just a newbie to this site.

For this question, can I find all connected components and assign each node a component id, then answer yes to a query if two nodes have the same component id and answer no otherwise?

Or I need to find out the path as well?

id=4834282094723072