Union Find实现Is Graph Bipartite（二着色）代码报错求排查

• Find方法缺失路径压缩且逻辑错误
  原find方法中，当parent[x] != x时直接返回parent[x]，这根本没找到真正的根节点，只是返回了父节点。正确的find需要递归或迭代找到根，同时做路径压缩，这样才能保证后续操作的正确性和效率。修正后的find方法如下：

  public int find(int x) {
      if (parent[x] != x) {
          int origParent = parent[x];
          parent[x] = find(parent[x]); // 路径压缩
          // 更新偏移量：x到新根的偏移 = x到原父的偏移 ^ 原父到新根的偏移（模2等价于异或）
          colorOffset[x] ^= colorOffset[origParent];
      }
      return parent[x];
  }
  

• 颜色管理逻辑错误：应该记录相对颜色偏移量而非绝对颜色
  你的colors数组存的是每个节点的绝对颜色，但Union Find处理二分图时，应该记录每个节点相对于其根节点的颜色偏移量（比如0表示和根同色，1表示不同色）。因为当合并两个连通分量时，需要根据两个节点的关系，调整整个分量的偏移量，而不是只改单个节点的颜色。原代码中只修改x或y的颜色，它们的子节点颜色没有同步更新，导致后续判断出错。

• 同一连通分量内的判断逻辑错误
  当x和y已经在同一连通分量时，你直接比较colors[x]和colors[y]是否相同，但正确的逻辑应该是：相邻节点的相对颜色应该不同（即colorOffset[x] ^ colorOffset[y] == 1）。如果相同，说明存在奇数环，不是二分图。

修正后的完整代码 #

package org.code;

public class TwoColorable {

    public static void main(String[] args) {
        int[][] edges = { { 1, 3 }, { 0, 2 }, { 1, 3 }, { 0, 2 } };
        TwoColorable tc = new TwoColorable();
        System.out.println(tc.twoColorable(edges)); // 输出true
    }

    public boolean twoColorable(int[][] edges) {
        int n = edges.length;
        UnionFind uf = new UnionFind(n);
        for (int i = 0; i < n; i++) {
            for (int neighbor : edges[i]) {
                if (!uf.union(i, neighbor)) {
                    return false;
                }
            }
        }
        return true;
    }

    private class UnionFind {
        int[] parent;
        int[] rank; // 按秩合并，优化合并效率
        int[] colorOffset; // 节点相对于根的颜色偏移：0=同色，1=不同色

        public UnionFind(int n) {
            parent = new int[n];
            rank = new int[n];
            colorOffset = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
                rank[i] = 1;
                colorOffset[i] = 0; // 初始自己是根，偏移量为0
            }
        }

        public int find(int x) {
            if (parent[x] != x) {
                int origParent = parent[x];
                parent[x] = find(parent[x]); // 路径压缩，直接指向根
                // 更新偏移量：x到新根的偏移 = x到原父的偏移 ^ 原父到新根的偏移
                colorOffset[x] ^= colorOffset[origParent];
            }
            return parent[x];
        }

        public boolean union(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);

            if (rootX == rootY) {
                // 同一连通分量，检查相邻节点是否颜色不同（偏移量异或为1）
                return (colorOffset[x] ^ colorOffset[y]) == 1;
            }

            // 按秩合并，将小秩树合并到大秩树下，保持树的平衡
            if (rank[rootX] > rank[rootY]) {
                // 交换x/y和rootX/rootY，保证rootY的秩更大
                int temp = rootX;
                rootX = rootY;
                rootY = temp;
                temp = x;
                x = y;
                y = temp;
            }

            parent[rootX] = rootY;
            // 计算rootX相对于rootY的偏移量：x和y必须不同色，所以colorOffset[x] ^ colorOffset[y] ^ 1
            colorOffset[rootX] = colorOffset[x] ^ colorOffset[y] ^ 1;

            if (rank[rootX] == rank[rootY]) {
                rank[rootY]++;
            }

            return true;
        }
    }
}

关键改进说明 #

1. 路径压缩与偏移量更新：find方法在路径压缩时，同步更新节点的颜色偏移量，确保每个节点的偏移量始终是相对于当前根节点的正确值。
2. 相对偏移量替代绝对颜色：用colorOffset数组记录节点与根的相对颜色关系，合并时只需调整根节点的偏移量，整个分量的节点会通过find自动同步。
3. 按秩合并：优化Union Find的合并效率，避免树退化成链表。
4. 正确的连通分量内判断：同一分量内的相邻节点，通过偏移量异或判断是否符合二分图颜色规则。

内容的提问来源于stack exchange，提问作者Spindoctor