I have solved the problem in java. The java solution based on DFS is there in my blog learn with me : Krishna K: Graph Problem based on Traversal (DFS)

I was missing initially one thing which prevented my solution from getting all test cases clear was depending upon the edges to add the nodes. By this I was ignoring the nodes which were lonely nones , not connected to any other nodes. Above link in my blog is completed corrected solution which passes all test cases.