[Huzurdaddi]

When you walk the graph you simply do a BFS on the graph and then color each node as you visit it and never revisit a node which is colored.

One easy method of programming this is to take a random node and push all of it's neighbors onto a stack. Then for each element on the stack check to see if the node is colored if so then ignore if not then push all of it's neighbors on the stack, bump the global count and color the node. Repeat. If at the end the global count is equal to the number of nodes in the graph then it is fully connected. A decent interview question.

The order of this is O(m) ( where m is the number of edges ). When I said the order was O(n^3) I was assuming that n~m this may not be a valid assumption. Clearly in a fully connected graph m = n^2. But most maps in dominions do not match that profile.

PS: I used the word "walk" in my 1st post which was incorrect. I should have defined what I meant which I did in this post sorry about being unclear.