Two undirected graphs $G$ and $H$ on the vertices $1,2,\ldots,n$ are disjoint if the intersection of their edge sets is empty. Assume both $G$ and $H$ are represented by adjacency matrices.
Describe an efficient algorithm that decides if $G$ and $H$ are disjoint. What is the complexity of your algorithm? Justify the correctness of your algorithm and your complexity claim.
What I am thinking is just picking an arbitrary vertex on either graph like $G$ and checking if we can reach a vertex from the other graph $H$ by running some simple traversal like DFS. Is there a better way? I am thinking what if we go through the adjacency matrix of one graph and check if any edge connects a vertex from one graph to the other.