\documentclass[letterpaper]{article}

\pagestyle{myheadings}

\markright{University of Calgary}

\usepackage{amsfonts}

\usepackage{amsmath}

\usepackage{courier}

\usepackage[margin=0.5in]{geometry}

\usepackage[hidelinks=true,pdftitle={University of Calgary Team Reference Document}]{hyperref}

\usepackage{listings}

\usepackage{multicol}

\usepackage{parskip}

\usepackage{tikz}

\usetikzlibrary{arrows,intersections}

\usepackage[compact]{titlesec}

\lstset{

basicstyle=\ttfamily\footnotesize,

language=c++,

tabsize=4,

}

\setcounter{tocdepth}{3}

\setlength{\voffset}{0.5cm}

\setlength{\headsep}{0.5cm}

\newcommand{\rx}[1]{#1\hrule}

\begin{document}

\title{University of Calgary Team Reference Document}

\thispagestyle{myheadings}

\markright{University of Calgary}

\begin{multicols*}{2}

\section{General Tips}

\begin{itemize}

\item For g++, \texttt{\#include <bits/stdc++.h>} includes all standard headers.

\item The constant $\pi$ is usually built-in as \texttt{M\_PI}.

\item Use \texttt{ios\_base::sync\_with\_stdio(false)} if you are using C++ streams. Big speedup in some cases.

\end{itemize}

\end{multicols*}

\section{Geometry}

\subsection{Basic 2D Geometry}

\begin{tabular}{@{}p{9cm}p{9cm}@{}}

\rx{Basic definitions}

\begin{lstlisting}

const double EP = 1e-9; // do not use for angles

typedef complex<double> PX;

const PX BAD(1e100,1e100);

\end{lstlisting}

\rx{Cross/dot product, same slope test}

\vspace{1em}

\begin{lstlisting}

double cp(PX a, PX b) {return (conj(a)*b).imag();}

double dp(PX a, PX b) {return (conj(a)*b).real();}

bool ss(PX a, PX b) {return fabs(cp(a,b)) < EP;}

\end{lstlisting}

\rx{Orientation: $-1$=CW, 1=CCW, 0=colinear}

\begin{lstlisting}

// Can be used to check if a point is on a line (0)

int ccw(PX a, PX b, PX c) {

double r = cp(b-a, c-a);

if (fabs(r) < EP) return 0;

return r > 0 ? 1 : -1;

}

\end{lstlisting}

\rx{Check if $x$ is on line segment from $p_1$ to $p_2$}

\begin{lstlisting}

bool onSeg(PX p1, PX p2, PX x) {

// Sometimes 1e-14 may be a better choice here

return fabs(abs(p2-p1)-abs(x-p1)-abs(x-p2))<EP;

}

\end{lstlisting}

\rx{Angle between vectors ($0$ to $\pi$)}

\begin{lstlisting}

Use fabs(arg(x/y))

\end{lstlisting}

\rx{Reflect vector using line normal (unit vectors)}

\begin{tabular}{@{}p{5cm}p{4cm}@{}}

Orientation of $\hat n$ does not matter.

Use \texttt{r = n * n / (-v)}

&

\begin{tikzpicture}[baseline={(0,1)}]

\draw (0,0) -- (3,0);

\draw[triangle 45-] (1.5,1) -- (1.5,0);

\draw[-triangle 45] (0.5,1) -- (1.5,0);

\draw[triangle 45-] (2.5,1) -- (1.5,0);

\node[right] at (1.3,1.3) {$\hat n$};

\node[right] at (0.2,1.3) {$\hat v$};

\node[right] at (2.4,1.3) {$\hat r$};

\end{tikzpicture}

\end{tabular}

\rx{Intersection point of two lines}

\begin{lstlisting}

PX lineIntersect(PX p1, PX v1, PX p2, PX v2) {

// If exact same line, pick random point (p1)

if (ss(v1, v2)) return ss(v1, p2-p1) ? p1 : BAD;

return p1 + (cp(p2-p1,v2)/cp(v1,v2))*v1;

}

\end{lstlisting}

\rx{Point to line distance ($x$ to $p+\vec vt$)}

\begin{lstlisting}

double ptToLine(PX p, PX v, PX x) {

// Closest point on line: p + v*dp(v, x-p)

return fabs(cp(v, x-p) / abs(v));

}

\end{lstlisting}

\rx{Line segment $(a, b)$ to point $p$ distance}

\begin{lstlisting}

double lsp_dist(PX a, PX b, PX p) {

return dp(b-a, p-a) > 0 && dp(a-b, p-b) > 0 ?

abs(cp(b-a, p-a) / abs(b-a)) :

min(abs(a-p), abs(b-p));

}

\end{lstlisting}

&

\rx{Check if two line segments intersect ($p_1p_2$ and $q_1q_2$)}

\begin{lstlisting}

// WARNING UNTESTED - intersection point is tested

bool segIntersect(PX p1, PX p2, PX q1, PX q2) {

int o1 = ccw(p1, p2, q1);

int o2 = ccw(p1, p2, q2);

int o3 = ccw(q1, q2, p1);

int o4 = ccw(q1, q2, p2);

if (o1 != o2 && o3 != o4) return true;

// p1, p2 and q1 are colinear and q1 on p1p2

if (o1 == 0 && onSeg(p1, p2, q1)) return true;

// p1, p2 and q1 are colinear and q2 on p1p2

if (o2 == 0 && onSeg(p1, p2, q2)) return true;

// q1, q2 and p1 are colinear and p1 on q1q2

if (o3 == 0 && onSeg(q1, q2, p1)) return true;

// q1, q2 and p2 are colinear and p2 on q1q2

if (o4 == 0 && onSeg(q1, q2, p2)) return true;

return false; // Doesn't fall in above cases

}

\end{lstlisting}

\rx{Intersection point of two line segments ($p_1p_2$ and $q_1q_2$)}

\begin{lstlisting}

PX segIntersect(PX p1, PX p2, PX q1, PX q2) {

// Handle special cases for colinear

if (onSeg(p1, p2, q1)) return q1;

if (onSeg(p1, p2, q2)) return q2;

if (onSeg(q1, q2, p1)) return p1;

if (onSeg(q1, q2, p2)) return p2;

PX ip = lineIntersect(p1, p2-p1, q1, q2-q1);

return (onSeg(p1, p2, ip) && onSeg(q1, q2, ip))

? ip : BAD;

}

\end{lstlisting}

\rx{Area of polygon (including concave)}

\begin{lstlisting}

// points must be in CW or CCW order

double area(vector<PX> const& P) {

double a = 0.0;

for (int i = 0; i < P.size(); i++)

a += cp(P[i], P[(i+1)%P.size()]);

return 0.5 * fabs(a);

}

\end{lstlisting}

\rx{Centroid of polygon (including concave)}

\begin{lstlisting}

// points must be in CW or CCW order

PX centroid(vector<PX> const& P) {

PX c;

double scale = 0.0;

for (int i = 0; i < P.size(); i++) {

int j = (i+1) % P.size();

double x = cp(P[i], P[j]);

c += (P[i] + P[j]) * x;

scale += 3.0 * x;

}

return c / scale;

}

\end{lstlisting}

\end{tabular}

\begin{tabular}{@{}p{9cm}p{9cm}@{}}

\rx{Cut convex polygon with straight line}

\vspace{1mm}

Returns polygon on left side of $p+\vec vt$. Points can be in CW or CCW order. Do not use with duplicate points.

\begin{lstlisting}

vector<PX> pts;

void cutPolygon(PX p, PX v) {

auto P = pts; // make a copy

pts.clear();

for (int i = 0; i < P.size(); i++) {

if (cp(v, P[i]-p) > EP) pts.push_back(P[i]);

PX pr = P[(i+1)%P.size()],

ip = lineIntersect(P[i], pr - P[i], p, v);

if (ip != BAD && onSeg(P[i], pr, ip))

pts.push_back(ip);

// remove duplicate points

while (pts.size() >= 2 && norm(

pts[pts.size()-1] - pts[pts.size()-2]) < EP)

pts.pop_back();

}

}

\end{lstlisting}

\subsection{Convex Hull (Floating Point)}

Graham's scan. Complexity: $O\left(n\log n\right)$

\begin{lstlisting}

vector<PX> pts;

void convexHull() {

if (pts.empty()) return;

int fi = 0;

for (int i = 1; i < pts.size(); i++)

if (pts[i].imag() + EP < pts[fi].imag() ||

(fabs(pts[i].imag() - pts[fi].imag())<EP

&& pts[i].real() + EP < pts[fi].real()))

fi = i;

swap(pts[0], pts[fi]);

sort(++pts.begin(), pts.end(), [](PX a, PX b) {

PX v1 = a - pts[0], v2 = b - pts[0];

double a1 = arg(v1), a2 = arg(v2);

// Use smaller epsilon for angles

if (fabs(a1 - a2) > 1e-14) return a1 < a2;

return abs(v1) < abs(v2);

});

int M = 2;

for (int i = 2; i < pts.size(); i++) {

while (M > 1 && ccw(pts[M-2], pts[M-1],

pts[i]) <= 0) M--;

swap(pts[i], pts[M++]);

}

if (M < pts.size()) pts.resize(M);

}

\end{lstlisting}

Notes:

\begin{itemize}

\item All intermediate colinear points and duplicate points are discarded

\item If all points are colinear, the algorithm will output the two endpoints of the line

\item Works with any number of points including 0, 1, 2

\item Works with line segments colinear to the starting point

\end{itemize}

Example usage

\begin{lstlisting}

pts.clear();

pts.emplace_back(0.0, 0.0); // put all the points in

convexHull();

// pts now contains the convex hull in CCW order

// starting from lowest y point

\end{lstlisting}

&

\rx{Check if point is within polygon}

\begin{lstlisting}

// P must be a convex/concave polygon sorted CCW/CW

bool inPolygon(vector<PX> const& P, PX p) {

double sum = 0.0;

for (int i = 0; i < P.size(); i++){

PX a = P[i], b = P[(i+1)%P.size()];

// to exclude edges, MUST return false

if (onSeg(a, b, p)) return true;

sum += arg((a-p) / (b-p));

}

// Use 1e-14 for angle

return fabs(fabs(sum) - 2.0*M_PI) < 1e-14;

}

\end{lstlisting}

\subsection{Convex Hull (Integer)}

Returns convex hull in CCW order starting from lowest $x$ point instead of $y$ point. Complexity: $O\left(n\log n\right)$

Note: Even for floating point, it might be better to use this line sweep method as it is more numerically stable.

\begin{lstlisting}

typedef long long LL;

typedef pair<LL,LL> PT;

vector<PT> pts;

LL ccw(PT a, PT b, PT c) {

return (b.first-a.first)*(c.second-a.second) -

(b.second-a.second)*(c.first-a.first);

}

void convexHull() {

vector<PT> b, t;

sort(begin(pts), end(pts));

for (PT pt : pts) {

// If you want to keep intermediate colinear

// points, use < and >

while (b.size() >= 2 && ccw(b[b.size()-2],

b[b.size()-1], pt) <= 0) b.pop_back();

while (t.size() >= 2 && ccw(t[t.size()-2],

t[t.size()-1], pt) >= 0) t.pop_back();

b.push_back(pt);

t.push_back(pt);

}

pts = b;

for (int i = int(t.size()-2); i > 0; i--)

pts.push_back(t[i]);

}

\end{lstlisting}

\end{tabular}

\section{Graphs}

\vspace*{-2em}

\begin{tabular}{@{}p{9cm}p{9cm}@{}}

\subsection{Articulation Points and Bridges}

Graph does not need to be connected. Tested only on bidirectional (undirected) graphs. Complexity: $O\left(V + E\right)$

\begin{lstlisting}

typedef vector<int> VI;

typedef vector<VI> VVI;

VVI adj;

VI dfs_low, dfs_num;

int cnt;

void dfs(int i, int r, int p) { // (cur, root, parent)

if (dfs_num[i] != -1) return;

dfs_low[i] = dfs_num[i] = cnt++;

int ap = i != r; // number of disconnected

// components if vertex is removed

for (int j : adj[i])

if (j != p) { // change cond if parallel edges

if (dfs_num[j] == -1) {

dfs(j, r, i);

if (dfs_low[j] >= dfs_num[i]) ap++;

if (dfs_low[j] > dfs_num[i]) {

// (i,j) is a bridge

// each **UNORDERED** pair

// will occur exactly once

}

dfs_low[i] = min(dfs_low[i], dfs_low[j]);

} else {

dfs_low[i] = min(dfs_low[i], dfs_num[j]);

}

}

if (ap >= 2) {

// i is an articulation point

// each vertex will only occur once

}

}

\end{lstlisting}

Example usage:

\begin{lstlisting}

// N is number of vertices

cnt = 0;

adj.assign(N, VI()); // fill adj

dfs_num.assign(N, -1);

dfs_low.resize(N); // initialization not necessary

for (int n = 0; n < N; n++) dfs(n, n, -1);

\end{lstlisting}

\subsection{Bellman-Ford}

Consider terminating the loop if no weight was modified in the loop. Complexity: $O(VE)$

\begin{lstlisting}

let weight[V] = all infinity except weight[source] = 0

let parent[V] = all null

loop V-1 times

for each edge (u,v) with weight w

if weight[u] + w < weight[v]

weight[v] = weight[u] + w

parent[v] = u

// detecting negative weight cycles

for each edge (u,v) with weight w

if weight[u] + w < weight[v]

then graph has negative weight cycle

\end{lstlisting}

\subsection{Cycle Detection in Directed Graph}

We can keep track of vertices currently in recursion stack of function for DFS traversal. If we reach a vertex that is already in the recursion stack, then there is a cycle in the graph.

&

\subsection{Dijkstra's}

Remember to consider using Floyd-Warshall or $O\left(V^2\right)$ version of Dijkstra's. Complexity: $O\left(\left(E+V\right)\log V\right)$

\begin{lstlisting}

typedef pair<int,int> PT;

typedef vector<PT> VPT;

vector<VPT> adj;

int dist[N]; // N = number of nodes

priority_queue<PT, vector<PT>, greater<PT>> dja;

dja.emplace(0, START_NODE);

fill(dist, dist+N, INT_MAX);

dist[START_NODE] = 0;

while (!dja.empty()) {

PT pt = dja.top(); dja.pop();

if (pt.first != dist[pt.second]) continue;

for (PT ps : adj[pt.second]) {

if (pt.first + ps.second < dist[ps.first]) {

dist[ps.first] = pt.first + ps.second;

dja.emplace(dist[ps.first], ps.first);

}

}

}

\end{lstlisting}

\subsection{Eulerian Cycle}

This non-recursive version works with large graphs.

Complexity: $O(E\log E)$

\begin{lstlisting}

vector<multiset<int>> adj;

vector<int> cyc;

void euler(int n) {

stack<int> stk;

stk.push(n);

while (!stk.empty()) {

n = stk.top();

if (adj[n].empty()) {

cyc.push_back(n);

stk.pop();

} else {

auto it = adj[n].begin();

int m = *it;

adj[n].erase(it);

adj[m].erase(adj[m].find(n));

stk.push(m);

}

}

}

\end{lstlisting}

Example usage:

\begin{lstlisting}

adj[0].insert(1); adj[1].insert(0); // 0 to 1

adj[0].insert(1); adj[1].insert(0); // another one

adj[0].insert(0); adj[0].insert(0); // loop on 0

cyc.clear();

euler(0); // find eulerian cycle starting from 0

// cyc contains complete cycle including endpoints

// e.g. 0, 0, 1, 0

\end{lstlisting}

\subsection{Floyd-Warshall}

Negative on diagonal means a vertex is in a negative cycle. Complexity: $O\left(V^3\right)$

\begin{lstlisting}

let dist[V][V] be initialized to

dist[v][v] = 0

dist[u][v] = weight of edge else infinity

for k from 1 to V

for i from 1 to V

for j from 1 to V

if dist[i][j] > dist[i][k] + dist[k][j]

dist[i][j] = dist[i][k] + dist[k][j]

\end{lstlisting}

\end{tabular}

\subsection{Bipartite Graphs}

\subsubsection{Maximum Bipartite Matching}

\begin{tabular}{@{}p{9cm}p{9cm}@{}}

Complexity: $O\left(VE\right)$

\begin{lstlisting}

vector<vector<int>> adj;

vector<char> visL, visR;

vector<int> matchR;

bool bpm(int l) {

if (visL[l]) return false;

visL[l] = true;

for (int r : adj[l]) {

if (matchR[r] == l) continue;

visR[r] = true;

if (matchR[r]<0 || bpm(matchR[r])) {

matchR[r] = l;

return true;

}

}

return false;

}

\end{lstlisting}

&

Example usage:

\begin{lstlisting}

int ans = 0; // cardinality

vector<int> U; // unmatched left vertices

matchR.assign(R, -1);

for (int l = 0; l < L; l++) {

visL.assign(L, 0);

visR.assign(R, 0);

if (bpm(l)) ans++; else U.push_back(l);

}

\end{lstlisting}

Minimum vertex cover is $\left(L-Z\right) \cup \left(R \cap Z\right)$

\begin{lstlisting}

visL.assign(L, 0);

visR.assign(R, 0);

for (int l : U) bpm(l);

for (int l = 0; l < L; l++) {

if (!visL[l]) then l is in vertex cover

}

for (int r = 0; r < R; r++) {

if (visR[r]) then r is in vertex cover

}

\end{lstlisting}

\end{tabular}

\vspace{-3em}

\begin{tabular}{@{}p{9cm}p{9cm}@{}}

\subsubsection{Stable Marriage/Matching}

Only tested with equal numbers of men and women.

Complexity: $O\left(MW\right)$

\begin{lstlisting}

typedef vector<int> VI;

vector<VI> mPref, wPref;

VI wPartner;

void stableMarriage() {

int M = mPref.size();

VI pr(M), fm(M);

iota(begin(fm), end(fm), 0);

wPartner.assign(wPref.size(), -1);

while (!fm.empty()) {

int m = fm.back();

int w = mPref[m][pr[m]++];

if (wPartner[w] == -1 || wPref[w][m]

< wPref[w][wPartner[w]]) {

fm.pop_back();

if (wPartner[w] != -1)

fm.push_back(wPartner[w]);

wPartner[w] = m;

}

}

}

\end{lstlisting}

Example usage:

\begin{lstlisting}

mPref.clear(); wPref.clear();

// Man 0 ranks women 2, 0, 1 (best to worst)

mPref.push_back(VI{2,0,1});

// Woman 0 ranks men 1, 2, 0 (best to worst)

wPref.push_back(VI{2,0,1});

stableMarriage(); // matching is in wPartner

\end{lstlisting}

&

\subsubsection{Notes}

\begin{itemize}

\item Konig's theorem: In any bipartite graph, the number of edges in a maximum matching equals the number of vertices in a minimum vertex cover.

\item The complement of a minimum vertex cover is a maximum independent set.

\item For minimum/maximum weight bipartite matching, use min cost max flow or Hungarian algorithm.

\item For minimum/maximum weight vertex cover, reduce to minimum cut (max flow).

\end{itemize}

\end{tabular}

\begin{tabular}{@{}p{9cm}p{9cm}@{}}

&

\subsection{Max Flow (with Min Cut)}

Dinic's algorithm.

Complexity: $O\left(\min\left(V^2E, fE\right)\right)$ where $f$ is the maximum flow

For unit capacities: $O\left(\min\left(V^{2/3}, E^{1/2}\right)E\right)$

For bipartite matching: $O\left(\sqrt VE\right)$

\begin{lstlisting}

typedef long long LL;

const int SOURCE=0, SINK=1; // change if necessary

struct edge {

int to, idx;

LL cap;

};

vector<vector<edge>> adj;

vector<int> lvl, ptr;

LL totalflow;

LL dfs(int n, LL f) {

if (n == SINK) { totalflow += f; return f; }

if (lvl[n] == lvl[SINK]) return 0;

while (ptr[n] < (int)adj[n].size()) {

edge& e = adj[n][ptr[n]];

ptr[n]++;

if (lvl[e.to] == lvl[n]+1 && e.cap > 0) {

LL nf = dfs(e.to, min(f, e.cap));

if (nf) {

e.cap -= nf;

adj[e.to][e.idx].cap += nf;

return nf;

}

}

}

return 0;

}

bool runMaxFlow() {

lvl.assign(adj.size(), -1);

ptr.assign(adj.size(), 0);

lvl[SOURCE] = 0;

queue<int> bfs;

bfs.push(SOURCE);

while (!bfs.empty()) {

int t = bfs.front();

bfs.pop();

for (edge& e : adj[t]) {

if (lvl[e.to] != -1 || e.cap <= 0) continue;

lvl[e.to] = lvl[t]+1;

bfs.push(e.to);

}

}

if (lvl[SINK] == -1) return false;

while (dfs(SOURCE, 1LL<<60)) {}

return true;

}

void initMaxFlow(int nodes) {

totalflow = 0; adj.clear(); adj.resize(nodes);

}

void addEdge(int a, int b, LL w) {

adj[a].push_back(edge{b, (int)adj[b].size(), w});

adj[b].push_back(edge{a, (int)adj[a].size()-1, 0});

}

\end{lstlisting}

Example usage

\begin{lstlisting}

initMaxFlow(desired number of nodes); // nodes 0 to N-1

addEdge(0, 3, 123); // 0 to 3 with capacity 123

while (runMaxFlow()) {}

// The max flow is now in totalflow

// The min cut: Nodes where lvl[i] == -1 belong to the T

// component, otherwise S

\end{lstlisting}

\end{tabular}

\subsection{Min Cost Max Flow}

Edmonds-Karp with Bellman-Ford algorithm. Complexity: $O\left(\min\left(V^2E^2, fVE\right)\right)$ where $f$ is the maximum flow

\begin{lstlisting}

const int NODES = 101 // maximum number of nodes

typedef long long LL;

typedef pair<int,int> PT;

vector<vector<int>> adj;

LL cap[NODES][NODES], cost[NODES][NODES], flow[NODES][NODES];

LL totalflow, totalcost;

bool runMCMF(int source, int sink) {

vector<LL> mf(NODES), weight(NODES, 1LL<<60); // must be larger than longest path

vector<int> parent(NODES, -1);

weight[source] = 0;

mf[source] = 1LL<<60; // value must be larger than max flow

for (int i = 0, lm = 0; i < NODES-1 && lm == i; i++) {

for (int u = 0; u < NODES; u++) {

for (int v : adj[u]) {

if (!cap[u][v] && !flow[v][u]) continue;

LL w = (flow[v][u]) ? -cost[v][u] : cost[u][v];

if (weight[u] + w < weight[v]) {

weight[v] = weight[u] + w;

parent[v] = u;

mf[v] = min(mf[u], (flow[v][u]) ? flow[v][u] : cap[u][v]);

lm = i+1;

}

}

}

}

LL f = mf[sink];

if (!f) return false;

for (int j = sink; j != source;) {

int p = parent[j];

if (flow[j][p]) {

cap[j][p] += f;

flow[j][p] -= f;

} else {

cap[p][j] -= f;

flow[p][j] += f;

}

totalcost += f * (weight[j] - weight[p]);

j = p;

}

totalflow += f;

return true;

}

void initMCMF() {

totalflow = totalcost = 0;

adj.clear(); adj.resize(NODES);

memset(cap, 0, sizeof cap);

memset(cost, 0, sizeof cost);

memset(flow, 0, sizeof flow);

}

void addEdge(int a, int b, LL w, LL c) {

adj[a].push_back(b);

adj[b].push_back(a); // this line is necessary even without bidirectional edges

cap[a][b] = w; // set cap[b][a] and cost[b][a] to the same to get bidirectional edges

cost[a][b] = c;

}

\end{lstlisting}

Example usage

\begin{lstlisting}

initMCMF();

addEdge(0, 3, 123, 5); // adds edge fron 0 to 3 with capacity 123 and cost 5

while (runMCMF(source, sink)) {}

// The max flow is now in totalflow and total cost in totalcost

\end{lstlisting}

\subsection{Strongly Connected Components}

Tarjan's algorithm. Note that Tarjan's algorithm generates SCCs in reverse topological order, while Kosaraju's algorithm generates in topological order. Complexity: $O\left(V + E\right)$

\begin{tabular}{@{}p{9cm}p{9cm}@{}}

\begin{lstlisting}

typedef vector<int> VI;

typedef vector<VI> VVI;

VVI adj;

VI dfsLow, dfsNum, sccNum, sccStack;

vector<char> vis;

int cnt, numScc;

void dfs(int i) {

if (dfsNum[i] != -1) return;

dfsLow[i] = dfsNum[i] = cnt++;

sccStack.push_back(i);

vis[i] = true;

for (int j : adj[i]) {

dfs(j);

if (vis[j])

dfsLow[i] = min(dfsLow[i], dfsLow[j]);

}

if (dfsLow[i] == dfsNum[i]) {

int j;

do {

j = sccStack.back();

sccStack.pop_back();

vis[j] = false;

sccNum[j] = numScc;

} while (i != j);

numScc++;

}

}

void scc() {

int N = adj.size();

cnt = numScc = 0;

dfsLow.resize(N); // init not necessary

dfsNum.assign(N, -1);

sccNum.resize(N); // init not necessary

vis.assign(N, false);

for (int n = 0; n < N; n++) dfs(n);

}

\end{lstlisting}

&

\subsubsection{2-SAT}

\begin{lstlisting}

vector<char> truthValues;

int VAR(int i) {return 2*i;}

int NOT(int i) {return i^1;}

int NVAR(int i) {return NOT(VAR(i));}

void addCond(int c1, int c2) {

adj[NOT(c1)].push_back(c2);

adj[NOT(c2)].push_back(c1);

}

void init2SAT(int numVars) {

adj.assign(2*numVars, VI());

truthValues.resize(numVars); // init not necessary

}

bool run2SAT() {

scc();

for (int i = 0; i < adj.size(); i += 2) {

if (sccNum[i] == sccNum[i+1]) return false;

// If SCC is computed with Kosaraju's, use > instead

truthValues[i/2] = sccNum[i] < sccNum[i+1];

}

return true;

}

\end{lstlisting}

Example usage

\begin{lstlisting}

init2SAT(N); // variables from 0 to N-1

addCond(VAR(4), NVAR(0)); // v4 or not v0

if (run2SAT()) {

// there is a solution

// truth values are in truthValues[0 to N-1]

}

\end{lstlisting}

\end{tabular}

\subsection{Tree Algorithms}

\subsubsection{Lowest Common Ancestor}

LCA can be solved using RMQ of the dfs tree (using sparse table or segment tree), or the following code using this binary-search like method. Complexity: $O\left(n\log n\right)$ preprocessing and $O\left(\log n\right)$ per query

\begin{lstlisting}

int N, // number of vertices

T[100000], // parent of each vertex (parent of root should be itself)

L[100000], // depth of each node from root (calculate with dfs or something)

P[100000][17]; // P[i][j] is the 2^j parent of i, or root if nonexistent [N][floor(log2(N))+1]

void lcaBuild() {

for (int n = 0; 1<<n <= N; n++)

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

P[i][n] = (n) ? P[P[i][n-1]][n-1] : T[i];

}

int lcaQuery(int p, int q) {

if (L[p] < L[q]) swap(p, q); // ensure p is deeper in tree

while (L[p] > L[q]) p = P[p][31 - __builtin_clz(L[p] - L[q])]; // get p on same level as q

if (p == q) return p; // special case if p/q is the LCA

for (int j = 31 - __builtin_clz(N); j >= 0; j--)

if (P[p][j] != P[q][j]) {p = P[p][j]; q = P[q][j];}

return T[p];

}

\end{lstlisting}

\begin{tabular}{@{}p{9cm}p{9cm}@{}}

\subsubsection{Eccentricity}

The maximum distances from every vertex are stored in \texttt{maxd}. Complexity: $O\left(V\right)$

\begin{lstlisting}

vector<vector<int>> adj;

int N, edged[N], maxd[N]; // N = number of vertices

int dfs1(int n, int p) {

edged[n] = 0;

for (int m : adj[n]) if (m != p)

edged[n] = max(edged[n], 1+dfs1(m, n));

return edged[n];

}

void dfs2(int n, int p, int pd) {

int maxEdged[2] = {pd, 0}, nwmg = 1;

for (int m : adj[n]) if (m != p) {

if (edged[m] + 1 > maxEdged[0]) {

maxEdged[1] = maxEdged[0];

maxEdged[0] = edged[m] + 1;

nwmg = 1;

} else if (edged[m] + 1 == maxEdged[0]) {

nwmg++;

} else if (edged[m] + 1 > maxEdged[1]) {

maxEdged[1] = edged[m] + 1;

}

}

for (int m : adj[n]) if (m != p) {

int npd = maxEdged[0];

if (npd == edged[m] + 1 && nwmg == 1)

npd = maxEdged[1];

dfs2(m, n, npd+1);

}

maxd[n] = max(pd, maxEdged[0]);

}

\end{lstlisting}

Example usage (goes through each connected component):

\begin{lstlisting}

memset(edged, -1, sizeof edged);

for (int n = 0; n < N; n++) if (edged[n] == -1) {

dfs1(n, -1);

dfs2(n, -1, 0);

}

\end{lstlisting}

\subsubsection{Number of times an edge is used in a path between two vertices}

Complexity: $O\left(V\right)$

\begin{lstlisting}

typedef pair<int,int> PT;

vector<PT> adj[N]; // pairs of (vertex, edge ID)

LL usage[E]; // usage of each edge ID is here

bool visited[N];

int dfs(int n){

visited[n] = true;

int nn = 1;

for (auto pt : adj[n]) {

if (visited[pt.first]) continue;

int x = dfs(pt.first);

usage[pt.second] += LL(N - x) * LL(x);

nn += x;

}

return nn;

}

\end{lstlisting}

&

\subsubsection{Heavy-Light Decomposition}

This code provides a basic framework for HLD.

\begin{lstlisting}

vector<vector<pair<int, int>>> adj;

const int MAXN = 10000;

int nChain [MAXN], // Chain number of vertex

nChainIndex[MAXN], // Index in chain of vertex

parent [MAXN], // Parent of a vertex

parentLen [MAXN], // Length of edge from parent

tSize [MAXN]; // Subtree size of a vertex

VI cDepth, // Depth of a chain (root is 0)

cLength, // Length of a chain

cParent; // Vertex number of chain parent

void dfs(int n, int p) {

tSize[n] = 1;

for (auto const& m : adj[n]) if (m.first != p) {

parent[m.first] = n;

parentLen[m.first] = m.second;

dfs(m.first, n);

tSize[n] += tSize[m.first];

}

}

void hld(int n, int p) {

nChainIndex[n] = cLength.back()++;

nChain[n] = (int)cLength.size()-1;

// Find largest child

int h = -1;

for (auto const& m : adj[n])

if (m.first != p &&

(h == -1 || tSize[m.first] > tSize[h]))

h = m.first;

if (h == -1) return;

hld(h, n);

// Process other children

for (auto const& m : adj[n])

if (m.first != p && m.first != h) {

cLength.push_back(0);

cParent.push_back(n);

cDepth.push_back(1+cDepth[nChain[n]]);

hld(m.first, n);

}

}

\end{lstlisting}

Example usage:

\begin{lstlisting}

cDepth.assign(1, 0);

cLength.assign(1, 0);

cParent.assign(1, -1);

dfs(0, -1);

hld(0, -1);

\end{lstlisting}

\subsubsection{Notes}

\begin{itemize}

\item The diameter of a tree (longest distance between two vertices) can be found by choosing any vertex, then finding a furthest vertex $v_1$, then finding a furthest vertex $v_2$. The distance between $v_1$ and $v_2$ is the diameter, and the centers (1 or 2) are median elements of that path.

\item The radius of a tree (longest distance from the best root) is $\left\lfloor\frac{diameter}2\right\rfloor$

\end{itemize}

\end{tabular}

\section{Sequences and Strings}

\subsection {AVL Tree}

Creating your own BST can be useful in certain situations; e.g. to find the kth element in a set in $O\left(\log n\right)$.

\begin{tabular}{@{}p{9cm}p{9cm}@{}}

\begin{lstlisting}

struct node {

node *l, *r;

int nodes, height, val;

node(int v)