LeetCode 785 Is Graph Bipartite?

Tag: 图算法 LeetCode Posted on 2022-02-08 22:52:35 Edited on 2022-02-08 23:35:17 Views: 156

概述

https://leetcode.com/problems/is-graph-bipartite/

递归法

拿到题目,感觉挺简单的,直接遍历图,遍历过程中设置标记,一共有两种标记,设置一个节点的邻居节点为与之不同的另一种标记。

如果出现已标记的节点不兼容则其非二分图。

实现过程中,不要一个数组承担多个作用,例如用 mark 同时记录是否访问过和设置的颜色,很容易实现错。

class Solution {
public:
    vector<bool> visited;
    vector<bool> mark;
    vector<vector<int>> graph;
    bool ans = true;
    bool isBipartite(vector<vector<int>>& graph) {
        vector<bool> visited(graph.size(), false);
        vector<bool> mark(graph.size(), false);
        this->graph = graph;
        this->visited = visited;
        this->mark = mark;
        for (int i = 0; i < graph.size(); i ++) {
            if (!visited[i]) helper(i);
        }
        return ans;
    }
    
    void helper(int i) {
        if (!ans) return;
        visited[i] = true;
        for (auto n : graph[i]) {
            if (visited[n]) { 
                if (mark[n] == mark[i]) {
                    ans = false;
                    return;
                }
            } else {
                mark[n] = !mark[i];
                helper(n);
            }
        }
    }
};

未经允许,禁止转载,本文源站链接:https://iamazing.cn/