This is actually a well researched characterization problem, where the family of graphs referred to as ‘good galaxies’ are in fact the halved hypercube graphs (here halving refers to the act of a ‘comet’ arriving). An exact characterization of this can be found here: http://www.fmf.uni-lj.si/~klavzar/preprints/NOVI.pdf
However for the given test cases, any heuristic involving cliques, or even the neighborhoods of the of vertices of the graph sufficed. I’ll let the editorial further explain this :).
If n is not a power of 2, the answer is no. If it is, we construct a hypercube with 2n
vertices and split it into two components(using an O(VE) algorithm) the way it is told in the problem and pick any of the connected components.
Since the connected component is vertex symmetric, we can relabel its vertices(in any way) to go from 1 to n and check whether its adjaceny matrix
is equal to that of the input graph.
Just checking the adjacency matrix isn’t sufficient for graph isomorphism in general. In fact I think you might be able to construct cases where the adj matrix looks the same but the graph isn’t a ‘good galaxy’. In this restricted version isomorphism can be checked by looking at cliques of a certain magnitude, though it is really hard to come up with this within the span of the contest.