How can I find multiple disconnected components in a graph?

I am trying to implement a problem on SPOJ - Herding , I have now got the basic idea of solving the problem but I am not getting the following. I use BFS from (0,0) till no more elements can be reached and mark the visited array. Then, how do I find the next index to start BFS from?, traversing through whole of visited array to find the unmarked position will definitely get me TLE. How to do this?

i solved this using union set data structure. if 2 nodes are meant to be connected just call union between and at the end just iterate over all nodes to find number of sets.

union can be done in O(log(n)), so complexity is kinda n**mlog(nm)

I’ve practiced union find algorithm, can you please tell the BFS method?

Read about “Flood-fill algorithm”. It is a DFS based algorithm.

Hey, i made something, see if it helps http://ideone.com/F8QNys :slight_smile:

//