785.md

785. Is Graph Bipartite?

Leetcode link

背景介绍

很调皮的一个题目

文字说明也很难懂。。。

简单来说题目提供一个二维数组，graph[0] 代表与第 0 个元素有无向边的元素集合，且每个两个元素之间最多有一条边，也有可能没有边

题目要求我们判断这个图是不是二分图：也就是能把图分成两个不相交的集合，使得同一集合的顶点之间不相连

解题思路——染色

我们把图染色，染色规则是：有边的两个点不能染同一个颜色

因为是二分图，所以我们的颜色有三种状态：0 表示未染色、1, -1 分别代表两种不同颜色

一旦发现有两个相邻的元素被染了同一个颜色，表示这个图不是二分图，返回 false

C++

class Solution {
 public:
  bool isBipartite(vector<vector<int>>& graph) {
    int n = graph.size();
    vector<int> colors(n);
    for (int i = 0; i < n; i++) {
      if (colors[i] == 0 && !valid(graph, 1, i, colors)) {
        return false;
      }
    }
    return true;
  }

  bool valid(vector<vector<int>>& graph, int color, int index,
             vector<int>& colors) {
    if (colors[index] != 0) {
      return colors[index] == color;
    }
    colors[index] = color;
    for (int i : graph[index]) {
      if (!valid(graph, -color, i, colors)) {
        return false;
      }
    }
    return true;
  }
};

Javascript

/**
 * @param {number[][]} graph
 * @return {boolean}
 */
var isBipartite = function(graph) {
     let n = graph.length;
    let colors = new Array(n).fill(0);
    for (let i = 0; i < n; i++) {
      if (colors[i] == 0 && !valid(graph, 1, i, colors)) {
        return false;
      }
    }
    return true;
};

var valid = function(graph, color, index, colors) {
    if (colors[index] != 0) {
      return colors[index] == color;
    }
    colors[index] = color;
    for (let i of graph[index]) {
      if (!valid(graph, -color, i, colors)) {
        return false;
      }
    }
    return true;
}

解题思路——并查集

与前面的染色思路相近，我们把连接到同一个节点的节点集合划分到一个组：graph[0] 是一个组，graph[1] 也是一个组。。。

接下来，我们只需要判断同一个组里的元素是否有相邻就好，如果有，则不是二分图

举个例子： graph[0] 的元素跟元素 0 如果在同一个组，则表示这个图不是二分图

C++

class UnionFind {
 private:
  vector<int> root;
  vector<int> rank;

 public:
  UnionFind(int size) : root(size), rank(size) {
    for (int i = 0; i < size; i++) {
      root[i] = i;
      rank[i] = 1;
    }
  }

  int find(int x) {
    if (x == root[x]) {
      return x;
    }
    return root[x] = find(root[x]);
  }

  void unionSet(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);
    if (rootX != rootY) {
      if (rank[rootX] >= rank[rootY]) {
        root[rootY] = rootX;
        rank[rootX] += rank[rootY];
      } else {
        root[rootX] = rootY;
        rank[rootY] += rank[rootX];
      }
    }
  }
};

class Solution {
 public:
  bool isBipartite(vector<vector<int>>& graph) {
    int n = graph.size();
    UnionFind uf(n);
    for (int i = 0; i < n; i++) {
      for (int j : graph[i]) {
        //   i 与 j 相邻，所有不应该在同一组
        if (uf.find(i) == uf.find(j)) {
          return false;
        }
        // 将连向同一个元素的元素都划分为一组
        uf.unionSet(graph[i][0], j);
      }
    }
    return true;
  }
};

JS

class UnionFind {
 constructor(size) {
     this.root = new Array(size);
     this.rank = new Array(size);
    for (let i = 0; i < size; i++) {
      this.root[i] = i;
      this.rank[i] = 1;
    }
  }

  find(x) {
    if (x == this.root[x]) {
      return x;
    }
    return this.root[x] = this.find(this.root[x]);
  }

  unionSet(x, y) {
    let rootX = this.find(x);
    let rootY = this.find(y);
    if (rootX != rootY) {
      if (this.rank[rootX] >= this.rank[rootY]) {
        this.root[rootY] = rootX;
        this.rank[rootX] += this.rank[rootY];
      } else {
        this.root[rootX] = rootY;
        this.rank[rootY] += this.rank[rootX];
      }
    }
  }
};
var isBipartite = function(graph) {
    let n = graph.length;
    let uf = new UnionFind(n);
    for (let i = 0; i < n; i++) {
      for (let j of graph[i]) {
        //   i 与 j 相邻，所有不应该在同一组
        if (uf.find(i) === uf.find(j)) {
          return false;
        }
        // 将连向同一个元素的元素都划分为一组
        uf.unionSet(graph[i][0], j);
      }
    }
    return true;
};