DP on Graphs

DP on Graphs

tip

Make sure you know the basics of graphs, DFS, topological sorting, SCC and DP before moving towards this section.

  1. Read the sections 16.2, 16.3, 16.4, 18.1 and 18.3 from CPH book to understand DP on graphs, successor / functional graphs and binary lifting.

  2. Go through the algorithm for finding LCA of two nodes in any tree using binary lifting and binary search from here

Session slides

  1. Day 1 - DP on graphs, DP on directed graph with cycles, successor/functional graphs, binary lifting, Floyd's cycle detection algorithm (Hare and tortoise algorithm) for successor graphs

Additional Resource

  1. If you want to learn more about DP on trees, through some problems, you can refer this CF blog

Practice Problems

  1. CSES - Game Routes
  2. Codechef - Visiting Friends
  3. CSES - Planets Queries I
  4. CSES - Company Queries I
  5. CSES - Planets Cycles
  6. Hackerrank - Detect cycle in a linked list
  7. Leetcode - Linked list cycle II
  8. 1020/B - Badge
  9. SPOJ - DAGCNT2
  10. 918/D - MADMAX
  11. CSES - Investigation
Edit this page