🟡 剑指 Offer II 106. 二分图

LeetCode 提示

题目难度 中等

原题链接 🔗 leetcode

题解1

class Solution {    private boolean flag = true;    private Map<Integer, Integer> visited = new HashMap<>();
    private void dfs(int cur, int nxt, int[][] graph) {      if (!flag) {        return;      }      var curVisited = visited.get(cur);      if (curVisited == null) {        visited.put(cur, nxt);        for (int nextNode: graph[cur]) {          dfs(nextNode, 1-nxt, graph);        }      } else if (curVisited != nxt) {        flag = false;        return;      }    }
    public boolean isBipartite(int[][] graph) {      int start = 0;            for (int i=0; i<graph.length; i++) {        if (visited.get(i) == null) {          dfs(i, 0, graph);        }      }
      return flag;    }}