LeetCode 886 Possible Bipartition

标签: 图算法 LeetCode 发布于:2022-02-08 23:59:54 编辑于:2022-02-09 00:11:58 浏览量:889

概述

https://leetcode.com/problems/possible-bipartition/

递归法

注意两点:

  1. 这里人群的标号是从 1 开始的,不是 0;
  2. 对于 a 不喜欢 b,构建图时我们不能只有一条 a 到 b 的边,b 到 a 的边也必须有, 因为我们到时候遍历的时候可能并不是从 a 的方向过来的。
class Solution {
public:
    vector<vector<int>> graph;
    vector<bool> visited;
    vector<bool> mark;
    bool ok = true;
    bool possibleBipartition(int n, vector<vector<int>>& dislikes) {
        // build graph
        vector<vector<int>> graph(n + 1);
        for (auto dislike : dislikes) {
            graph[dislike[0]].push_back(dislike[1]);
            graph[dislike[1]].push_back(dislike[0]);
        }
        vector<bool> visited(n + 1, false);
        vector<bool> mark(n + 1, false);
        this->mark = mark;
        this->visited = visited;
        this->graph = graph;
        
        for (int i = 1; i <= n ; i ++) {
            if (!visited[i]) helper(i);
        }
        return ok;
    }
    
    void helper(int i) {
        if (!ok) return;
        visited[i] = true;
        for (auto n : graph[i]) {
            if (visited[n]) {
                if (mark[n] == mark[i]) {
                    ok = false;
                    return;
                }
            } else {
                mark[n] = !mark[i];
                helper(n);
            }
        }
    }
};

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