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:

     	/*
     	* 1. Declaration of a vector
     	* 2. Inserting element at the end in vector v
     	* 3. v.size() gives number of elements in a vector
     	* 4. Sorting a vector
     	*/
     	#include<bits/stdc++.h>
     	using namespace std;
     	void print_vector(vector<int>& v){
     	for(int i = 0 ; i < v.size() ; i ++){ // 3
     	cout << v[i] << " " ;
     	}
     	}
     	int main(){
     	vector<int> v; // 1
     	int x = 100, y = 20;
     	v.push_back(x); // 2
     	v.push_back(y);
     	print_vector(v); // Output : 100 20
     	sort(v.begin(), v.end()); // 4
     	print_vector(v); // Output : 20 100
     	}

     view raw vector.cpp hosted with ❤ by GitHub
     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.

     	/*
     	* 1. Declaration of a pair of a char and an integer
     	* 2. Initializing pair with char 'c' and int 3
     	* 3. p1.first returns the value of first data type
     	* 4. p1.second returns the value of second data type
     	*/
     	#include<bits/stdc++.h>
     	using namespace std;
     	int main(){
     	pair<char, int> p1 = make_pair('c', 3); // 1, 2
     	cout << p1.first << endl; // 3
     	cout << p1.second << endl; // 4
     	}

     view raw pair.cpp hosted with ❤ by GitHub
   • 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++:
   

   	#include<bits/stdc++.h>
   	using namespace std;
   	int main(){
   	map<int , vector< pair<int, int > > > adjList; // Seems like torture xD
   	/***********Explanation************
   	* Abstract form of a map = map< key, value >
   	* Here key = int,
   	* Value = vector of pairs
   	* Key is actually a node(let's say N) of graph here and
   	* Value is the vector containing all the nodes which are
   	* connected to N directly.
   	* Why we need pair< d1, d2 > ?
   	* d2 = node connected to N directly.
   	* d1 = weight of edge between N and d2.
   	* For unweighted graph we can use only int instead of pair
   	* or we can keep value 0 for all edges if we use pair of
   	* int like shown below.
   	*************************************/
   	// Suppose we are given number of edges 'n' and all the edges in form of (u, v).
   	// So we can use a for loop to scan inputs.
   	int n;
   	cin >> n;
   	for(int i = 0 ; i < n ; i ++){
   	int u, v;
   	cin >> u >> v;
   	// If graph is undirected:
   	/* 1. */ adjList[u].push_back(make_pair(0, v));
   	/* 2. */ adjList[v].push_back(make_pair(0, u));
   	// If edge is directed from u to v
   	// Then no need to write 2nd statement.
   	}
   	// Print Adjacency List
   	for(map<int , vector< pair<int, int > > >::iterator it = adjList.begin() ; it != adjList.end() ; it++){
   	cout << it->first << " : ";
   	vector<pair<int, int> > neighbours = it->second;
   	for(int i = 0 ; i < neighbours.size() ; i++){
   	cout << "(" << neighbours[i].first << " " << neighbours[i].second << ")";
   	}
   	cout << endl;
   	}
   	}

   view raw adjList.cpp hosted with ❤ by GitHub
   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 !