Lowest Common Ancestor – Tarjan’s off-line algorithm
We have a tree $G$ with $n$ nodes and we have $m$ queries of the form $(u, v)$. For each query $(u, v)$ we want […]
Month: August 2021
Solve RMQ (Range Minimum Query) by finding LCA (Lowest Common Ancestor)
Given an array A[0..N-1]. For each query of the form [L, R] we want to find the minimum in the array A starting from position L and ending with position R. We will […]
Lowest Common Ancestor – Farach-Colton and Bender Algorithm
Let $G$ be a tree. For every query of the form $(u, v)$ we want to find the lowest common ancestor of the nodes $u$ […]
Lowest Common Ancestor – Binary Lifting
Let $G$ be a tree. For every query of the form (u, v) we want to find the lowest common ancestor of the nodes u and v, i.e. we want […]
Lowest Common Ancestor
1. Lowest Common Ancestor – $O(\sqrt{N})$ and $O(\log N)$ with $O(N)$ preprocessing Given a tree $G$. Given queries of the form $(v_1, v_2)$, for each […]
Finding the Eulerian path in $O(M)$
A Eulerian path is a path in a graph that passes through all of its edges exactly once. A Eulerian cycle is a Eulerian path […]
Finding a negative cycle in the graph
You are given a directed weighted graph $G$ with $N$ vertices and $M$ edges. Find any cycle of negative weight in it, if such a […]
Checking a graph for acyclicity and finding a cycle in $O(M)$
Consider a directed or undirected graph without loops and multiple edges. We have to check whether it is acyclic, and if it is not, then […]
Prüfer code
In this article we will look at the so-called Prüfer code (or Prüfer sequence), which is a way of encoding a labeled tree into a sequence of […]
Kirchhoff’s theorem. Finding the number of spanning trees
Problem: You are given a connected undirected graph (with possible multiple edges) represented using an adjacency matrix. Find the number of different spanning trees of […]
Second best Minimum Spanning Tree – Using Kruskal and Lowest Common Ancestor
A Minimum Spanning Tree $T$ is a tree for the given graph $G$ which spans over all vertices of the given graph and has the […]
Minimum spanning tree – Kruskal with Disjoint Set Union
For an explanation of the MST problem and the Kruskal algorithm, first see the main article on Kruskal’s algorithm. In this article we will consider the […]
Minimum spanning tree – Kruskal’s algorithm
Given a weighted undirected graph. We want to find a subtree of this graph which connects all vertices (i.e. it is a spanning tree) and […]
Minimum spanning tree – Prim’s algorithm
Given a weighted, undirected graph $G$ with $n$ vertices and $m$ edges. You want to find a spanning tree of this graph which connects all […]
Number of paths of fixed length / Shortest paths of fixed length
The following article describes solutions to these two problems built on the same idea: reduce the problem to the construction of matrix and compute the […]
Floyd-Warshall – finding all shortest paths
Given a directed or an undirected weighted graph $G$ with $n$ vertices. The task is to find the length of the shortest path $d_{ij}$ between […]
D´Esopo-Pape algorithm
Given a graph with $n$ vertices and $m$ edges with weights $w_i$ and a starting vertex $v_0$. The task is to find the shortest path […]
Bellman-Ford Algorithm
Single source shortest path with negative weight edges Suppose that we are given a weighted directed graph $G$ with $n$ vertices and $m$ edges, and […]
Dijkstra on sparse graphs
For the statement of the problem, the algorithm with implementation and proof can be found on the article Dijkstra’s algorithm. 1. Algorithm We recall in the […]
