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 the standard tree dp for this question with a slight modification!!!

the standard dp is with the following state $$$dp[cur][cur taken]$$$ where cur is the current node. if $$$child$$$ is the child of $$$cur$$$ in the tree, our transition is as follows:

$$$dp[cur][1] = a_{cur}+dp[child][0]$$$ $$$dp[cur][0] = \max(dp[child][0], dp[child][1])$$$

now instead of the standard dp state, we can modify our dp into $$$dp[cur][cur taken][a taken][b taken]$$$. since our removed edge is $$$a \rightarrow b$$$, our rule also applies that we cannot take both $$$a$$$ and $$$b$$$ which is not dealt with in the original tree dp. thus, after we run the tree dp, our new state allows us to track if we take $$$a$$$ and $$$b$$$, and we cannot take both. our new dp transition will look like the following:

$$

thus, if after we run our dp, if the root of our component is $$$rt$$$, our maximum value for that component is $$$\max_{i,j,k=0{0,1}} dp[rt][i][j][k]$$$ where $j+k \neq 2}.

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.

also note 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 :)