Official Analysis (C++)

Explanation

Assume that we have a valid solution composed of $K$ connected components in our graph.

Let's look at one of these connected components, which could look something like this:

However, for each of the $K$ connected components, the grass types can be inverted and still be a valid solution:

There are $2$ possible ways to arrange each connected component. Thus, if there's $k$ connected components, there's $2^k$ ways to arrange the entire graph.

Note how the nodes force their adjacen t ones to have a specific coloring, so if any two nodes don't satisfy this condition, it's impossible. Otherwise, the solution will always be $2^k$.

Implementation

Copy
import java.io.*;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Revegetate {
	public static int[] type;
	public static boolean impossible;
	public static ArrayList<Integer>[] same;
	public static ArrayList<Integer>[] diff;