[系列文章] leetcode每日一题785

发布于 12 天前  25 次阅读


785. Is Graph Bipartite?

Description

There is an undirected graph with n nodes, where each node is numbered between 0 and n - 1. You are given a 2D array graph, where graph[u] is an array of nodes that node u is adjacent to. More formally, for each v in graph[u], there is an undirected edge between node u and node v. The graph has the following properties:

  • There are no self-edges (graph[u] does not contain u).
  • There are no parallel edges (graph[u] does not contain duplicate values).
  • If v is in graph[u], then u is in graph[v] (the graph is undirected).
  • The graph may not be connected, meaning there may be two nodes u and v such that there is no path between them.

A graph is bipartite if the nodes can be partitioned into two independent sets A and B such that every edge in the graph connects a node in set A and a node in set B.

Return true if and only if it is bipartite.

sample1
  • Input: graph = [[1,2,3],[0,2],[0,1,3],[0,2]].
  • Output: false.
  • Explanation: There is no way to partition the nodes into two independent sets such that every edge connects a node in one and a node in the other.

Solution

判断二分图的经典解法,着色法,使用两种颜色,相邻节点颜色不同,若发生冲突则不是二分图。遍历过程使用广搜或深搜均可,下面使用广度优先搜索。

Code

class Solution {
    static constexpr int UNCOLORED = 0;
    static constexpr int RED = 1;
    static constexpr int BLACK = -1;
public:
    bool isBipartite(vector<vector<int>>& graph) {
        int n = graph.size();
        vector<int> color(n, 0); // record color of each node.
        for (int j = 0; j < n; j++) {
            if (color[j] == UNCOLORED) {
                queue<int> nodes;
                nodes.push(j);
                color[j] = RED;
                while (!nodes.empty()) {
                    int v = nodes.front();
                    nodes.pop();
                    for (int i = 0; i < graph[v].size(); ++i) {
                        int vx = graph[v][i];
                        if (color[vx] == 0) {
                            color[vx] = -color[v];
                            nodes.push(vx);
                        } else if (color[vx] == color[v]) {
                            return false;
                        }
                    }
                }
            }
        }
        return true;
    }
};