Test cases
N3K2
Returns24
The 24 different graphs are shown below. In each picture, the vertices have labels 1, 2, 3 from the left to the right.
N15K2
Returns789741546
N100K1
Returns1
N1K3
Returns3
N100K3
Returns
492594064
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
There can be at most 3 colors. So how about we solve for 3 colors, then we can adapt the solution for fewer number of colors with small tweaks.
The problem statement describes the decision as first choosing colors and then creating the edges. But the actual rules for counting the unique setups combines the two together. Let’s try to make the decision about picking a color AND an edge for each vertex.
Imagine we’ve already picked colors and edges for the firstnodes, let’s decide the-th node. We can pick one of 3 colors:
Pick color A. Now we have to decide the edge. We can choose to connect vertexto any of the previous vertices as long as they have a different color. Since this is a counting problem, let’s keep in mind the counts for each color (assume 3 colors) :. We cannot connect to color, so there arevertices we can connect this vertex to. There is an additional option: Don’t connect the vertex at all. This givesoptions. Note that later vertices don’t need to know what edge we picked, only the color.If we pick color B: There areoptions in case color C is picked.
The idea is that we can just increment the count of the respective color and move on to the next. Also note that, because there werevertices so the sum of all colors must be. This helps us do a dynamic programming solution. Let’s nameto the number of ways to pick colors and edges for vertices starting fromonwards, assuming there werevertices of each color among the firstvertices.
Base case:. This means that we have already made a decision for all the vertices and there is nothing else to do. One way to do nothing: The result is 1.Else there are 3 options:We can pick color. This meansoptions for the edge. The number ofvertices is incremented. Between picking the edge and picking the next colors/edges we have two independent decisions, so we multiply:.The addition of these 3 values is the result for.Fewer colors
When there are two colors, we can just disable the part where we pick color. The state can still be, butwill always be 0.
影子依旧可以相亲相爱。哪一块骨骼最温暖，总能一击即中。
