Piyush Nirala

Search This Blog

Differences between Set, Multi-set, Unordered_set, Unordered_multi-set

Posted by Piyush Nirala May 20, 2020

Get link
Facebook
Twitter
Pinterest
Email
Other Apps

Tabular Representation

STL C++

Get link
Facebook
Twitter
Pinterest
Email
Other Apps

Comments

Binary Lifting Technique and the Least Common Ancestor Problem

Finding LCA using 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 to find a node w that lies on the path from u to the root node, that lies on the path from v to the root node, and if there are multiple nodes we pick the one that is farthest away from the root node. In other words the desired node w is the lowest ancestor of u and v . In particular if u is an ancestor of v , then u is their lowest common ancestor. A naïve approach would be something as follows:- To calculate the LCA of two nodes first we will bring both the nodes to the same height by making the node with greater depth jump one parent up the tree till both the nodes are at the same height. Once, both the nodes are at the same height we can then start jumping one parent up for both the nodes simultaneously till both the nodes become equal and that node will be the LCA of the two originally gi

Constructing a Graph/Tree in C++

Graph is a data structure that consists of following two components: 1. A finite set of vertices also called as nodes. 2. A finite set of ordered pair of the form (u, v) called as edge. The pair is ordered because (u, v) is not same as (v, u) in case of a directed graph(di-graph). The pair of the form (u, v) indicates that there is an edge from vertex u to vertex v. The edges may contain weight/value/cost. A tree is a special graph in which, if there exists any path between two nodes, then that is the only path. In easy language a tree can be said as a graph with no cycles. Tree is basically used to store data in a hierarchical form. An undirected graph with 5 vertices and 7 edges. In this article I am going to tell how to construct a tree/graph in your codes: Following two are the most commonly used representations of a graph. 1. Adjacency Matrix 2. Adjacency List Adjacency Matrix: Adjacency Matrix is a 2D array of size V x V where V is the number of vertices in a graph. Let the

Catalan Numbers

Before jumping to this topic, lets take a popular problem : The Handshake Problem We have N persons sitting on a round table. Any person can do a handshake with any other person. 1 2 3 4 Handshake with 2-3 and 1-4 will cause cross. In how many ways these N people can make handshakes so that no two handshakes crosses each other . N would be even. For example, in above diagram, there are two non-crossing ways to handshake {{1, 2}, {3, 4}} and {{1, 3}, {2, 4}}. Or we can say : There are 2n people sitting on a round table. In how many ways can they shake their hands, in pairs, without crossing the hands? Lets collect data for n=1, n=2, n=3,..... So, we got a sequence of numbers i.e 1, 2, 5, 14 ..... & famous Recurrence relation for them is : C n + 1 = C 0 C n + C 1 C n − 1 + ⋯ + C n C 0 = k = 0 ∑ n C k C n − k These are the Catalan Numbers. The n th Catalan number is given directly in terms

Powered by Blogger

Differences between Set, Multi-set, Unordered_set, Unordered_multi-set

Comments

Post a Comment