نظریه گرافها برای المپیاد کامپیوتر
Basic Definitions
Introduction to Graphs and Graph Modeling
Types of Graphs
Graph Implementation
Walks, Trails, Paths, Extremal
Subgraphs
Connectivity, Cut Edge, and Cut Vertex
Bipartite Graph
Trees
Introductory Properties
Distance in Tree and Graph
Counting the Number of Trees
DFS
BFS
Algorithm for Finding Tree Diameter
DFS Start/Finish Time
Cut Vertex and Bridge Algorithms
Idea Cultivation Workshop
Directed Graph
Definitions
Tournament
Directed Acyclic Graph
Strongly Connected Components
Detecting Cycles in a Directed Graph
Games and Directed Graphs
Functional Graphs and Permutation Graphs
Proof Techniques for Graph Problems
Extremal Choices
Contracting
Graph and Magic
Eulerian Tour 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
Matrices
Matrices and Operations on Them
Determinants of Matrices
Incidence Matrix
Adjacency Matrix
Number of Walks of Length n
Obtaining Recursive Functions Using Graphs and Matrices
Tree Data Structures
Binary Tree
Binary Search Tree (BST)
Heap
DSU
Segment Tree
Trie
NP and NP-complete Problems
NP and NP-complete Definitions
Proof of NP-Completeness of the SAT Problem
Graph NP-Complete Problems
Lca
Problem Description
O(n+q*lg(n)) Solution using Heavy-Light Decomposition
Tarjan's Offline Algorithm
Relationship between LCA and RMQ
LCA Linear Time Solution
Virtual Tree
Advanced Tree Algorithms
Minimum Spanning Tree
Sack
Centroid
Huffman Coding
Tree Hashing
Heavy-Light Decomposition (HLD)
Connectivity
Cuts and Connectivity
k-connected Graph
Max-Flow Min-Cut
Matching
Introduction
Matching in Bipartite Graphs
Min-Max Theorems
Applications
Maximum Flow and Matching
Poset
Matching in General Graphs
Special Topics
Planar Graph
Degree Sequence
Coloring
Identical Graphs
Random Walk
Ramsey Numbers
Independent Set and Clique
2-SAT
Several Special Matrices
Appendix
How to Use This Book?
Introduction to Algorithms and Complexity
Cheat Sheet
Index
Lca
Problems
Change Language (Farsi)
Source
Lca
¶
Problem Description
Ancestor at Specific Height Problem
Lowest Common Ancestor Problem
Relationship Between These Two Problems
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
Solution for the K-th Ancestor Problem
Solution for the LCA Problem
Relationship between LCA and RMQ
Converting RMQ to LCA
Linear-Time Cartesian Tree Construction
Converting LCA to RMQ
Solving RMQ with Sparse Table
LCA Linear Time Solution
Virtual Tree
Why is the Virtual Tree important to us?
First Problem
Diameter of a Subset
Algorithm
Introduction
First Attempt
A Better Algorithm
Optimal Order?
Implementation
Previous
Next