Best data structure for mapping between nodes and (known) cliques in a graph, that is easily updated after bisection?

Thank you for supplying this solution!

What I meant is that my current solution is not a one liner but is very inefficient, as in: it creates a bottle neck in my application.

I will try your solution and suggestnions and see if it is faster. Will take me a while thought to integrate it into the rest of my code.
In any case: thank you!