VU_SyntaxError

Page |1

int power(int base, int pow)

int ans = 1;

while (pow)

if (pow & 1)

ans = (1LL * ans % mod * base % mod) % mod;

base = 1LL * base * base % mod;

pow >>= 1;

return ans;

bool isPrime(int n) {

if (n <= 1) return false;

if (n <= 3) return true;

if (n % 2 == 0 || n % 3 == 0) return false;

for (int i = 5; i * i <= n; i += 6) {

if (n % i == 0 || n % (i + 2) == 0)

return false;

return true;

int knapsack(int i, int w)

{
VU_SyntaxError
Page |2

if (i < 0 || w <= 0)

return 0;

if (dp[i][w] != -1)

return dp[i][w];

if (weight[i] <= w)

int willTake = knapsack(i - 1, w - weight[i]) + val[i];

int notTake = knapsack(i - 1, w);

dp[i][w] = max(willTake, notTake);

return dp[i][w];

else

dp[i][w] = knapsack(i - 1, w);

return dp[i][w];

Graph

#include <bits/stdc++.h>

using namespace std;

void bfs(vector<int> adjList[], bool visited[], int nodes)

queue<int> q;

q.push(0);

visited[0] = true;

while (!q.empty())

int val = q.front();

q.pop();

cout << val << ' ';

for (auto i : adjList[val])

if (!visited[i])

q.push(i);

visited[i] = true;

int main()

int nodes, edges;

cin >> nodes >> edges;

vector<int> adjList[nodes];

while (edges--)

int a, b;

cin >> a >> b;

adjList[a].push_back(b);

adjList[b].push_back(a);

bool visited[nodes];

memset(visited, false, sizeof(visited));

bfs(adjList, visited, nodes);

}
VU_SyntaxError
Page |4

BFS ON GRID

#include <bits/stdc++.h>

using namespace std;

char grid[105][105];

bool visited[105][105];

int dx[] = {-1, 1, 0, 0};

int dy[] = {0, 0, -1, 1};

int n, m;

bool isValid(int x, int y)

if (x < 0 || x >= n || y < 0 || y >= m)

return false;

return true;

void BFS(int x, int y)

queue<pair<int, int>> q;

q.push({x, y});

visited[x][y] = true;

while (!q.empty())

pair<int, int> p = q.front();

q.pop();

cout << p.first << ' ' << p.second << endl;

for (int i = 0; i < 4; i++)

{
VU_SyntaxError
Page |5

int newX = p.first + dx[i];

int newY = p.second + dy[i];

if (isValid(newX, newY) && !visited[newX][newY])

q.push({newX, newY});

visited[newX][newY] = true;

int main()

cin >> n >> m;

for (int i = 0; i < n; i++)

for (int j = 0; j < m; j++)

cin >> grid[i][j];

int x, y;

cin >> x >> y;

memset(visited, false, sizeof(visited));

BFS(x, y);

sortest distance

#include <bits/stdc++.h>

using namespace std;

char grid[105][105];

bool visited[105][105];

int dx[] = {-1, 1, 0, 0};

int dy[] = {0, 0, -1, 1};

int dist[105][105];

int n, m;

bool isValid(int x, int y)

if (x < 0 || x >= n || y < 0 || y >= m)

return false;

return true;

void shortestDistance(int x, int y)

queue<pair<int, int>> q;

q.push({x, y});

visited[x][y] = true;

dist[x][y] = 0;

while (!q.empty())

pair<int, int> par = q.front();

q.pop();

for (int i = 0; i < 4; i++)

int childX = par.first + dx[i];

int childY = par.second + dy[i];

if (isValid(childX, childY) && !visited[childX][childY] )

q.push({childX, childY});

visited[childX][childY] = true;

dist[childX][childY] = dist[par.first][par.second] + 1;

int main()

cin >> n >> m;

for (int i = 0; i < n; i++)

for (int j = 0; j < m; j++)

cin >> grid[i][j];

int x, y;

cin >> x >> y;

memset(visited, false, sizeof(visited));

memset(dist, -1, sizeof(dist));

int destinationX, destinationY;

shortestDistance(x, y);

cout << dist[destinationX][destinationY];

single source sortest distance

#include <bits/stdc++.h>
VU_SyntaxError
Page |8

using namespace std;

vector<int> adjList[1000];

bool visited[1000];

int level[1000];

void bfs(int source)

queue<int> q;

q.push(source);

visited[source] = true;

level[source] = 0;

while (!q.empty())

int val = q.front();

q.pop();

for (auto i : adjList[val])

if (!visited[i])

q.push(i);

visited[i] = true;

level[i] = level[val] + 1;

int main()

int nodes, edges;

cin >> nodes >> edges;

adjList[nodes];

while (edges--)

int a, b;

cin >> a >> b;

adjList[a].push_back(b);

adjList[b].push_back(a);

memset(visited, false, sizeof(visited));

memset(level, -1, sizeof(level));

int source, destination;

cin >> source >> destination;

bfs(source);

cout<<level[destination];

}
VU_SyntaxError
P a g e | 10

C++ STL + Number Theory + Algorithms

Ordered Map (map<key, val>)

map<int, int> m;

m[5] = 10; // Insert

m.count(5); // 0 or 1

m.find(5); // Iterator to key or m.end()

m.erase(5); // Remove by key

for (auto [k,v] : m) cout << k << " " << v;

Unordered Map (unordered_map<key, val>)

unordered_map<int, int> um;

Set / Multiset / Unordered Set

#include <set> / <unordered_set>

set<int> s; multiset<int> ms; unordered_set<int> us;

s.insert(x); s.erase(x); s.find(x); s.count(x);

ms.count(x); ms.erase(ms.find(x)); // only one instance

Stack / Queue / Deque

#include <stack>, <queue>, <deque>

stack<int> st; queue<int> q; deque<int> dq;

st.push(x); st.pop(); st.top();

q.push(x); q.pop(); q.front();

dq.push_front(x); dq.push_back(x);

dq.pop_front(); dq.pop_back();

Priority Queue (Heap)

priority_queue<int> maxpq;

priority_queue<int, vector<int>, greater<int>> minpq;

Common String Functions

#include <string>
VU_SyntaxError
P a g e | 11

string s = "abcde";

s.size(), s.length(); // Length of string

s.substr(1,3); // "bcd" (start, length)

s.find("cd"); // Returns index or npos

s.erase(2,1); // Erase 1 char at pos 2

s.insert(2, "xyz"); // Insert at index 2

reverse(s.begin(), s.end());

stoi("123"); // to int

to_string(45); // int to string

count(s.begin(), s.end(), 'a'); // freq of 'a'

STL Algorithms (from <algorithm>)

sort(v.begin(), v.end());

reverse(v.begin(), v.end());

count(v.begin(), v.end(), val);

max_element(v.begin(), v.end());

min_element(v.begin(), v.end());

accumulate(v.begin(), v.end(), 0);

binary_search(v.begin(), v.end(), x);

lower_bound(v.begin(), v.end(), x);

upper_bound(v.begin(), v.end(), x);

Number Theory

__gcd(a, b); // Built-in GCD

lcm = a / __gcd(a,b) * b;

bool isPrime(int n) {

if (n < 2) return false;

for (int i = 2; i*i <= n; i++)

if (n % i == 0) return false;

return true;