java - Time out in Roads and Libraries on HackerRack -

i've been working on hackerrank problem time now, , can't seem understand why code timing out large input sizes. i've implemented adjacency list hash map cut down time, , have been using stack dfs, standard optimize it's run time. basic strategy here use dfs remove group of connected node, , continue doing until there none left (my dfs removes nodes reached), problem there ~80,000 disconnected parts per graph after take out single nodes no neighbors (so dfs called 80,000 times). there particularly better strategy here?

  static int numdisconnected(hashmap<integer, list<integer>> adj)  {     int result = 0;     list<integer> iter = new arraylist<>(adj.keyset());     (int k : iter) {       if (adj.get(k).size() == 0)  {         adj.remove(k);         result++;       }     }     hashmap<integer,boolean> explored = new hashmap<>();     (int : adj.keyset())  {       explored.put(i,false);     }     while (!adj.keyset().isempty())  {       result++;       depthfirstsearch(adj,explored);     }     return result;   } 

as point of reference, code takes 1.5 seconds run on machine ~2mb file input.

generally, you're doing close, hashmap<integer, list<integer>> data structure task. you're doing redundant work both keeping explored list , deleting adjacency map in numdisconnected , in depthfirstsearch (in earlier version of question). either of these should enough implement depth first search.

i tweaked algorithm not removing adj, changing explored boolean[] , using explore disconnected component, , find next node start dfs when component done.

it passed, no need preprocessing step of removing unconnected nodes.

(sorry paraphrasing instead of posting code, i'd rather not spoil it)