Disjoint-Set Data Structure (Union Find Algorithm)

Explain the working of disjoint-set data structure and efficiently implement it.   Problem: We have some number of items. We are allowed to merge any two items to consider them equal. At any point, we are allowed to ask whether two items are considered equal or not.

Check if given digraph is a DAG (Directed Acyclic Graph) or not

Given an directed graph, check if it is a DAG (Directed Acyclic Graph) or not. A DAG is a digraph (directed graph) that contains no cycles.   Below graph contains a cycle A-B-D-A, so it is not DAG. If we remove edge 3-0 from it, it will become a DAG.

2-Vertex Connectivity in the graph

Given a undirected connected graph, check if the graph is 2-vertex connected or not.   A connected graph G is said to be 2-vertex-connected (or 2-connected) if it has more than 2 vertices and remains connected on removal of any vertices. Any such vertex whose removal will disconnected the graph is called Articulation point.

2-Edge Connectivity in a Graph

Given a undirected connected graph, check if the graph is 2-edge connected or not.   A connected graph is 2-edge-connected if it remains connected whenever any edges is removed. A bridge or cut arc is an edge of a graph whose deletion increases its number of connected components. i.e. whose removal disconnects the graph. So if any such bridge exists, the …

Convert HashMap to TreeMap in Java

In this post, we will see how to convert HashMap to TreeMap in Java. The resultant TreeMap should contain all mappings of the HashMap, sorted by their natural ordering of keys.

Transitive Closure of a Graph

Given a digraph G, the transitive closure is a digraph G’ such that (i, j) is an edge in G’ if there is a directed path from i to j in G. The resultant digraph G’ representation in form of adjacency matrix is called the connectivity matrix.