Given N vertices and M edges find if two nodes are in the same connected component?
The problem is that you want to do a graph traversal every check : that is way too often.

Do a graph traversal to find the connected component of each vertex (e.g. give them a number). This takes $O(m+n)$ time. Store these numbers in an array indexed by the vertices, let's call it $A$. Then check if two vertices $i$ and $j$ are in the same connected component in $O(1)$ time by checking whether $A[i] = A[j]$.