hello. I have noticed after solving a few problems that there is little to no documentation on this topic, thus, I have decided to write a short blog. this is my first educational blog so please excuse me if there are errors.

note that this is simply an extension of dp on a tree, so it is strongly recommended you study dp on a tree before reading this blog.

firstly, a functional graph is defined as a directed graph where each vertices has exactly one outgoing edge. a key feature of these graphs is that in a connected functional graph, there is always one and only one cycle present. a proof is attached here. this is crucial to our dp later.

now, let us find an example problem to apply this topic. the problem can be summarized as the following:

Given $$$n$$$ people, person $$$i$$$ can donate $$$a_i$$$ but will not donate if there is a person $$$b_i$$$ which donates. Find the most amount of money that can be donated.

we can model the problem using directed edges from a person to the person they hate, making this a functional graph. we also notice that we can rephrase the problem into:

You are given a functional graph of $$$N$$$ vertices each with a value $$$a_i$$$. You cannot take two adjacent vertices. Find the maximum value we can achieve,

but there is a problem: we cannot directly run dp on each component since there is a cycle. thus, we will revisit our property earlier that there is only one cycle. the key insight lies in that if we remove one edge present in the cycle, our remaining component will be a tree ($$$n-1$$$ edges, $$$n$$$ vertices, fully connected). to find the cycle itself, we can run dfs from any vertice in the component, and it will eventually a node which it already visited, which is the cycle. we can let this edge, which is in the cycle be $$$a \rightarrow b$$$.

we will then remove the edge and now, we can run tree do!!! but instead of the standard dp state $$$dp[cur][cur taken]$$$ where cur is the current node, we can modify our dp into $$$dp[cur][taken][a taken][b taken]$$$.

note that there is also an edge case where the cycle in the connected component is of length $$$2$$$. in this case, we will obviously not delete the edge as the cycle itself is an edge.

notice that their may be multiple components in our graph, where each component is an individual connected functional graph. thus, we can run this dp for each component and sum up to find the final answer.

I am sure there are easier ways to set up the dp but that is the way which I found most intuitive.

thank you for reading :)