LeetCode 886 Possible Bipartition

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

概述

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

递归法

注意两点：

这里人群的标号是从 1 开始的，不是 0；
对于 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);
            }
        }
    }
};

Links: leetcode-886-possible-bipartition