In first question of Round E Google Kickstart | Why did I get TLE for DFS solution? Is it because of not using fast io

here is the question

and here is my code…

I have seen submissions of some other coders they have passed both the test cases with dfs solution…

I will check your code. For time being, this gave me AC:-
Found all connected components, added the weights of their spanning trees, finally I connected all those components using red edges.
AC code:-https://docs.google.com/document/d/1V1NGuwGiPC5D_yeRgDAZSa5RW1v-n9eN2-DlnB-9SlY/edit?usp=drivesdk

You are passing count everywhere…I think that is creating problems for you.

really? call by reference can give TLE??
this is bad
so making variable global is the solution?

in your accepted code…you haven’t used fast io still it got accepted… so this is not an issue definitely
I saw jeel_vaishnav’s code as well…
He did the same dfs… but not call by reference as i did.
this is so frustrating.
https://www.ideone.com/4z0MLA this is his code…

most of the coders have used union find I know.

Can you please confirm this or give some source that using call by reference can give TLEs…

No idea. But I know that if you want to count something, people mostly declare count as global to avoid any confusion…

The most likely reason for TLE is that you have passed adj by value.
Try passing adj by reference and the code should easily run in time limit.
Why is that so?
When passing by value a complete copy of a data structure is made before it gets passed. So for every call Complexity is the size of the adj DS.
Whereas pass by reference would work on the same original copy of the DS.

Added a & before the adj in the dfs function and you got AC in both large and small testset.

1 Like

I think using DSU in first problem was much more intuitive than using DFS . Because all one had to do was ignore the edges that form cycle in a connected component while taking the input of edges.
Here is the accepted code - https://ideone.com/kHgVsR

1 Like