c++ - 这行代码通过bfs在二分图算法中做了什么？

Question

我一直在阅读 https://cp-algorithms.com/graph/bipartite-check.html 的二分算法我遇到了一行:

side[u] = side[v] ^ 1

这行代码做了什么？ ^1 是什么意思？

尝试谷歌搜索但没有得出任何结果。

Answer 1

^ 是 bitwise xor C++ 中的运算符(也包括 C、Java 等)。

位 (0/1) 与 1 的按位异或翻转该位，即

0 ^ 1 = 1
1 ^ 1 = 0

维基百科上给出的

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.

在这个算法中，它被用来决定节点 u 应该属于哪个集合。
由于u和v是相连的(因为u在v的邻接表中)，所以 u 应该属于与v 不同的集合(二部图的属性)。
这些集合被记录在 side[] 数组中，该数组为两个不相交的顶点集存储 0 或 1，并将 -1 作为未初始化的值。