I have been reading bipartite algorithm from https://cp-algorithms.com/graph/bipartite-check.html and I encounter a line:
side[u] = side[v] ^ 1
What does this line of code do? What does ^1 means?
Tried googling it but didn't come up with any result.
^ is a bitwise xor operator in C++ (also in C, Java etc).
Bitwise xor of a bit(0/1) with 1 flips that bit, i.e.
0 ^ 1 = 1
1 ^ 1 = 0
As given on wikipedia
The bitwise XOR may be used to invert selected bits in a register (also called toggle or flip). Any bit may be toggled by XORing it with 1.
In this algorithm, it is being used to decide the set in which node u should belong.
As u and v are connected (because u is in the adjacency list of v), so u should belong to the different set as v (property of bipartite graph).
The sets are being recorded in the side[] array which stores 0 or 1 for the two disjoint set of vertices, and -1 as uninitialized value.