Well, your dfs function copies g every time, resulting in TLE. What you can do is to pass it by reference or have it global. Same goes for dfs2 and also the map in dfs2.