Help with USACO Grass Planting

Problem: USACO

I understand that by finding the maximum degree of any node in the graph+1, you can find the number of grass types needed if adjacent nodes must be grassed differently. But the problem also stipulates that all farms connected by a common farm cannot be grassed similarly either. How does the degree solution extend to this constraint as well>

This isn’t true. If you only need to consider adjacent nodes then two types suffice.

1 Like