By Daniel (9th grade)
Bessie’s Function
https://usaco.org/index.php?page=viewproblem2&cpid=1497
You can turn this into a graph problem. Each node points to a[node]. The resulting graph is many cycles with trees attached to each node. This type of graph is called a functional graph.
You want to make each node point to itself or point to someone that points to itself. To do this, you can use dp. First you do dp on each tree. The state is dp[node][0/1] where it’s 0 when you change the next one and 1 when you change it to point to itself. After you finish doing the dp on the trees, you can do dp on the cycles starting from any node. You have to add another state, which is if you changed the first node to 1 because this affects the last node in the cycle.
This sounds pretty scary to code, but it’s not that bad and it only requires 97 lines of code. Time complexity: O(N)
