I suggest you should know operations/usage of both, and then decide which one is easier according to Q. Time v/s Easy-to-code is a thing which varies from Q to Q and the methods should generally be decided by you.
You said that you usually use maps, means you must be finding it easier to code with it. But yes, its kind of slower too. So yes, there will be variations. You’d see sometimes its better to go for saving time, so at others you’d see the code becomes lot easier to code at cost of few milliseconds.
Since I haven’t actually started graph theory atm, I cant give a more detailed answer. So yeah, I would also like to hear from others regarding this.
Yesterday I was also working on a problem and my code was completely right but was failing on one test case due to TLE. Using unordered_map sorted out the problem and my code got AC.
EDIT: Following links will be visible as the contest ends.
If you deal or use the map<> then it will be bad for you. It’s complexity in worst case would be O(log(n)) unlike in vector it would be only constant. So you can easily generalise that why the hell map<> is slower than the vector.
So i advice you to use only vector in adjacency list. You can use unordered_map<> instead of map<> if it’s possible because unordered_map<> complexity would be amortised constant.
For more reference about complexity of any function. Click on this and scrawl for any query.
Okay, I think I get this now. And since map is O(log[N]), there shouldn’t be a significant difference in complexity if N is small. Is it possible to give some approximate value of how small? 10^4? or still lower?
Also, when we say its “O(log N)”…whats the base? 10 or 2 or e?