Dynamic Creation of Graphs for competitive programming

  In competitive programming, usually STL is used for faster programming and there the problem when we need to create dynamic array if we represent the graph by adjacency list.


in most of Visual studio, the only option is using new operator which is not very useful in competitive programming.

here is alternative way to make a graph using vector of  vector instead of array


in case we need to create a graph of  (n+1) nodes when we have taken "n" as input.


// vector of vector for adjacency list.

vector<vector<long long int>> adjlist;

adjlist.resize(n+1);   // it will help to create a graph of (n+1) nodes.


// input the edges

for (long long int i = 0; i < m; i++) {

long long int u;

long long int v;


cin >> u >> v;


adjlist[u].push_back(v);

adjlist[v].push_back(u);

}


//Visited array for DFS

vector<long long int> visited(n + 1);

for (long long int i = 0; i <= n; i++) visited[i] = -1;


//Standard DFS Code.

visited[0] = 0;

queue<long long int> q;

q.push(0);

while (!q.empty()) {

long long int curr = q.front();

q.pop();

for (int j : adjlist[curr]) {

if (visited[j] >= 0) continue;

visited[j] = visited[curr] + 1;

q.push(j);

}

}

Comments

Post a Comment

Popular posts from this blog

Aggressive cow

  #include<iostream> #include <vector> #include<string> #include<queue> #include<algorithm> #include <unordered_map>   using namespace std ; typedef long long int ll ;     bool possible ( vector < int > v, ll mid, ll k ) {   int last ; int cnt = 0 ; last = v [ 0 ] ; cnt ++ ; for ( int i = 1 ; i < v. size ( ) ; i ++ ) { if ( v [ i ] - last >= mid ) { cnt ++ ; last = v [ i ] ;   if ( cnt == k ) return true ; } }   if ( cnt >= k ) return true ; else return false ;         }     int main ( ) {     int t ; cin >> t ; while ( t -- ) {   int n, k ; cin >> n >> k ;   vector < int > v ( n, 0 ) ;   for ( int i = 0 ; i < n ; i ++ ) cin >> v [ i ] ;   sort ( v. begin ( ) , v. end ( ) ) ;   long long int resul...
Read more

LRU Cache Implementation

 // LRU Cache implementation #include <iostream> #include <unordered_map> using namespace std; class DLLNode { public: int key; int value; DLLNode *next; DLLNode *prev; DLLNode(int k, int v) { this->key = k; this->prev = NULL; this->value = v; this->next = NULL; } }; //Data structure and globals unordered_map<int, DLLNode*> cache; int Size =0; int capacity; DLLNode * head = new DLLNode(-1, -1); DLLNode * tail = new DLLNode(-1, -1); void addNodeAtHead(DLLNode *node) { node->prev = head; node->next = head->next; head->next->prev = node; head->next = node; return; } void removeNode(DLLNode* node) { DLLNode* prev = node->prev; DLLNode* next = node->next; prev->next = next; next->prev = prev; } int removeFromTail() { DLLNode* temp = tail->prev; removeNode(temp); return temp->key; } void moveToHead(DLLNode *node) { cout << "access this key" << node->key...
Read more

Segmentation Tree

#include< iostream > #include< string > #include< vector > #include< algorithm > using namespace std ; void Build ( int arr [], int segtree [], int s , int e , int index ) {      if ( s == e ) {         segtree [ index ] = arr [ s ];      }      else {          int mid = ( s + e ) / 2 ;         Build ( arr , segtree , s , mid , 2 * index );         Build ( arr , segtree , mid + 1 , e , 2 * index + 1 );          if ( segtree [ 2 * index ] < segtree [ 2 * index + 1 ])             segtree [ index ] = segtree [ 2 * index ];          else    ...
Read more