我一直在阅读 https://cp-algorithms.com/graph/bipartite-check.html 的二分算法我遇到了一行:
side[u] = side[v] ^ 1
这行代码做了什么？ ^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 作为未初始化的值。
关于c++ - 这行代码通过bfs在二分图算法中做了什么？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/56863729/