Is-A? Has-A? Who Knowz-A?

This problem asks you to determine whether two given nodes have a given relationship.

There are two relationships defined between individual nodes.

Is-A and Has-A.

Is-A extends only transitively.

Has-A extends transitively, but also can contain is-A relationships, and MUST contain at least 1 has-a relationship.

So problem boils down to determining whether we have a path from one node to another using either only is-A edges, or all edges.

Create the graph and run BFS, right?

O(q*(e+v))....too slow when 10k queries, and 10k edges.

Intuition: small number of nodes with lots of queries....need to be able to query in constant time. Can we do some preprocess work? Like computing all relationships in a single pass? Do we know any graph algorithms that compute all paths in a single pass?

Run floyd warshall. Set initial distance to 1 if a path exists. run twice. once for is a, once for has a. Perform all queries in constant time

O(500^3) is fast enough.