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
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 […]
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 […]
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 […]
Finding articulation points in a graph in $O(N+M)$
We are given an undirected graph. An articulation point (or cut vertex) is defined as a vertex which, when removed along with associated edges, makes […]
Finding Bridges Online
1. Overview We are given an undirected graph. A bridge is an edge whose removal makes the graph disconnected (or, more precisely, increases the number […]
Finding bridges in a graph in $O(N+M)$
We are given an undirected graph. A bridge is defined as an edge which, when removed, makes the graph disconnected (or more precisely, increases the […]
Finding the nearest pair of points
1. Problem statement Given $n$ points on the plane. Each point $p_i$ is defined by its coordinates $(x_i,y_i)$. It is required to find among them […]
Finding area of simple polygon in $O(N)$
Let a simple polygon (i.e. without self intersection, not necessarily convex) be given. It is required to calculate its area given its vertices. 1. Method […]
Finding common tangents to two circles
Given two circles. It is required to find all their common tangents, i.e. all such lines that touch both circles simultaneously. The described algorithm will […]
Finding the equation of a line for a segment
The task is: given the coordinates of the ends of a segment, construct a line passing through it. We assume that the segment is non-degenerate, […]
Finding Power of Factorial Divisor
You are given two numbers $n$ and $k$. Find the largest power of $k$ $x$ such that $n!$ is divisible by $k^x$. 1. Prime $k$ […]
Finding the rank of a matrix
The rank of a matrix is the largest number of linearly independent rows/columns of the matrix. The rank is not only defined for square matrices. The […]
Finding repetitions
Given a string $s$ of length $n$. A repetition is two occurrences of a string in a row. In other words a repetition can be described by […]
Finding the largest zero submatrix
You are given a matrix with n rows and m columns. Find the largest submatrix consisting of only zeros (a submatrix is a rectangular area of the matrix). 1. […]
Finding Max/Min of a List or Collection
1. Introduction A quick intro on how to find the min/max value from a given list/collection with the powerful Stream API in Java8. 2. Find Max in […]
Finding the Differences Between Two Lists in Java
1. Overview Finding differences between collections of objects of the same data type is a common programming task. As an example, imagine we have a […]
