Hashing

Let’s first try to find the hash value of a graph with $n$ vertices, $m$ edges and no updates.

Observation 1: We can take at most one element from each of the connected components.

Observation 2. A vertice will appear in our result if the number of subsets where it appeared and the miniHash function didn't malfunction is odd.

Now, for each node how many such subsets are there? Let’s say sizes of all other subsets are $s_1, s_2,.....$

Then the number of subsets it appeared will be $(s_1+1)*(s_2+1)*......$

This will be odd only if all the connected components except this one are even in size.

Case analysis :

Case 1: There are more than one connected component with odd size. In this case, the answer will be 0 as every node will appear an even number of times.

Case 2: There is exactly one odd-sized connected component. In this case, the result will be XOR of all the nodes in that connected component.

Case 3: There are no odd-sized connected components. In this case, all nodes will appear in an odd number of subsets. So the answer will be XOR of all the nodes.

Now, for the given problem. We can use disjoint-set-union algorithm to keep track of the size of each connected component, also the odd-sized connected components. After that, we can use the observations discussed above to find the hash value of the current graph.

Complexity: $O(n*log(n))$