Skip to content

Latest commit

 

History

History
19 lines (10 loc) · 588 Bytes

functional-graph.md

File metadata and controls

19 lines (10 loc) · 588 Bytes

Functional Graph

  • Definition : A graph where every vertex has exactly one outgoing vertex.

You can think of every connected component of a functional graph as a rooted tree with all edges directed toward the root plus an additional edge going out of the root.

Ideas:

Given a functional graph tell where a vertex will land after following the edge K times. K < 10^12.

Solution : Binary Jumping

Reachablity in Functional Graph

Solution : Graph Coloring https://atcoder.jp/contests/abc357/tasks/abc357_e

Problems 2: https://codeforces.com/contest/1867/problem/D