Graph : Adjacency List using STL in C++ for competitve programming

CONTENTS :

1. Introduction to Adjacency List.
2. Some STL Componenets required to make Adjacency List:
• Vector
• Pair
• Map
3. Implementation in C++.

---

1. Introduction to Adjacency List : According to wikipedia: In graph theory and computer science, an adjacency list is a collection of unordered lists used to represent a finite graph. Each list describes the set of neighbors of a vertex in the graph. This is one of several commonly used representations of graphs for use in computer programs.
   We can solve many graph problems much efficiently using Adjacency list representation of a graph as compared to Adjacency Matrix. Example we can run DFS on adjacency List in O(E + V) time while it requires O(V * V) time for Adjacency Matrix. Here E = number of edges and V = number of vertices in a graph.
   We can create Adjacency list by making out own classes and functions like addEdge(), removeEdge() etc which is not a good practice in competitive programming because we don't have enough time to write a lot of stuff. So most of the programmers don't use such cumbersome method.
   Let's see what they use !
2. Some STL Componenets required to make Adjacency List:
   • Vector :Vectors are sequence containers representing arrays that can change in size. That's great ! we need not to specify the size of a vector. Let's see the implementation part: Click here if you want to learn more about vectors.
   • Pair : As the name suggests, it is a data structure that can contain a pair of either same or different data types.
   • Map : Hash Map in C++.Data is stored in the form of Key-Value pairs. We can insert, search, erase an element from map in O(logN) time.
     You can learn about maps(STL) on Geeks For Geeks.
     Practice this data structure on Hackerrank.
3. Implementation : Its the time to create our own adjacency list for the following graph using the above cool data structures in C++:
   
   Click here to see input and output for this program.
Remove all the comments from this program to see the actual length of this C++ program. :)
Congrats ! You now know how to create your Adjacency List in C++(in not more than 7-10 lines of code) for a given graph.

Hope this is useful for all my dear programmers.
Happy Coding !