نظریه گرافها برای المپیاد کامپیوتر
Basic definitions
Introduction and Modeling with Graphs
Types of Graphs
Graph Implementation
Walk, Trail, Path, Extremal
Subgraphs
Connectivity, Cut Edge, and Cut Vertex
Bipartite Graph
Trees
Basic Properties
Distance in Trees and Graphs
Counting the Number of Trees
DFS
BFS
گراف و نمایش ماتریسی آن
Directed Graphs
Undirected Graphs
Adjacency Matrix
Adjacency List
Edge List
Graph Representation
نمایش گراف
Depth-First Search (DFS)
الگوریتم جستجوی اول عمق (DFS)
Directed Graphs
الگوریتم جستجوی عمق اول (DFS)
Bipartite Graphs
Spanning Trees
Trees
الگوریتم جستجوی اول سطح (BFS)
ماتریس مجاورت
لیست مجاورت
لیست یالها
الگوریتم جستجوی اول سطح
BFS و DFS در یک گراف
تعاریف گراف
Representing a Graph Using an Edge List
گرافهای جهتدار
Introduction
Graph Representation
Graph Traversal
Important Algorithms
Algorithm for Finding the Diameter of a Tree
Checking Ancestor-Descendant Relationship in Linear Time
Finding the k-th Ancestor
Bi-connecting with Minimum Number of Paths
Vertex and Edge Cut Algorithms
Idea Cultivation Workshop
Directed graph
Definitions
Tournament
Directed Acyclic Graph (DAG)
Strongly Connected Components
Detecting Cycles in Directed Graphs
Games and Directed Graphs
Functional Graphs and Permutation Graphs
Proof technics in graph problems
Extremal Choices
Contraction
Graphs and Magic
Euler circuit and hamiltonian cycle
Introduction
Eulerian Tour in Directed and Undirected Graphs
De Bruijn sequence
Existence Theorems for Hamiltonian Cycles
Exponential Algorithms for Finding Hamiltonian Cycles and Paths
مسئله فروشنده دورهگرد (الگوریتم پویا)
Shortest path algorithms
Bellman-Ford
Dijkstra
Floyd-Warshall
Matrix
Matrices and Operations on Them
Kirchhoff's Theorem
Incidence Matrix
Adjacency Matrix
Number of Walks of Length n
Deriving Recursive Functions Using Graphs and Matrices
Tree data structures
Binary Tree
Binary Search Tree (BST)
Heap
DSU
Segment Tree
Search (Search)
Insertion (Insertion)
Applications
NP and NP-complete problems
Definition of NP and NP-Completeness
Problem Definitions
Reducing the circuit-sat Problem to sat
NP-Complete Graph Problems
LCA
Problem Statement
An O(n + q*lg(n)) Solution Using Heavy-Light Decomposition
Tarjan's Offline Algorithm
The Relationship Between LCA and RMQ
A Linear Approach to LCA
Virtual Tree
Advanced tree algorithms
Minimum Spanning Tree
Guni
Centroid
Huffman Coding
Tree Hash
Heavy-Light Decomposition (HLD)
Connectivity
Cuts and Connectivity
k-Connected Graph
Minimum Cut and Maximum Flow
Matching
Introduction
Matchings in Bipartite Graphs
Minimax Theorems
Applications
Maximum Flow and Matching
Poset
Matchings in General Graphs
Extra topics
Drawing a Planar Graph on a Sphere
Euler's Theorem
Dual Graph
Degree Sequence
Coloring
Isomorphism
Random Walk
Ramsey Numbers
Independent Set and Clique
مکمل گراف
2-SAT
Some Special Matrices
Appendix
چگونه از این کتاب استفاده کنیم؟
آشنایی با الگوریتم ها و پیچیدگی
برگه تقلب (Cheat sheet)
Index
LCA
Problems
Change Language
Source
LCA
¶
Problem Statement
The Problem of the Lowest Common Ancestor
The Relationship Between These Two Problems
An O(n + q*lg(n)) Solution Using Heavy-Light Decomposition
Heavy-Light Decomposition
Number of Light Edges on the Path to the Root
Solving the Problem of Ancestor at a Specific Height
Solving the LCA Problem
Tarjan's Offline Algorithm
The Solution to the LCA Problem
The Relationship Between LCA and RMQ
Converting RMQ to LCA
Building a Cartesian Tree in Linear Time
Converting LCA to RMQ
Solving RMQ with Sparse Table
A Linear Approach to LCA
Virtual Tree
Why is a Virtual Tree Important for Us?
The First Problem
Algorithm
Introduction
First Attempt
A Better Algorithm
Implementation
Previous
Next