Need help friends.
In graph problems I use map < int, vector< int> >adj to store adjacency list for that graph.
But recently I came across few examples where map seems to perform slow.
My question is whether I should continue using map or should I switch to vector< vector< int> > (or any other better thing) ?
Please Suggest.
Thank You
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. 
Number of vertices <= 10^5
This is the most common case. Use vector < int > adj[N]; where N is the number of vectices
Number of vertices <= 10^3 and you need to check whether there exits an edge between two edges in O(1)
Use bool a[N][N];
Example > CHFNFRN
You can also use
unordered_map<int,vector<int,int>>
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.
u can’t stick to one either it is map or vector.Try to learn and implement both.
Can you tell why? What effect did unordered keyword had? I am curious :3
It’s not a keyword but std::unordered_map is a different data structure in c++ like std::vector, std::map.
Check the edited answer
Thanks dear!
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?