leetcode 785. Is Graph Bipartite? 判断二分图-耗时100%

Problem: 785. Is Graph Bipartite? 判断二分图

解题过程

耗时100%，由于可能存在多个子树，所以每个子树都需要满足条件，拿到最大值n，然后使用状态数组，深度优先搜索dfs，若graph[i].size() > 0 && status[i]==false那么就是一颗子树，两个集合分别标记1或者2，标记从1开始，每次递归反转一次1-2，2-1，若存在两个相连的node的标记相同那么直接返回false

Code

class Solution { public: int group[101]; bool flag = true; void dfs(int node, vector<bool>& status, vector<vector<int>>& graph, int mark) { if(flag == false) return; status[node] = true; group[node] = mark; for(int i = 0; i < graph[node].size(); i++) { if(group[node]==group[graph[node][i]]) { flag = false; return; } if(status[graph[node][i]]==false) { dfs(graph[node][i], status, graph, (mark==1? 2:1) ); } } } bool isBipartite(vector<vector<int>>& graph) { int n = INT_MIN; for(int i = 0; i < graph.size(); i++) { for(int j = 0; j < graph[i].size(); j++) { n = max(n, graph[i][j]); } } if(n==INT_MIN) return true; n++; vector<bool> status(n, false); fill(group, group + 101, -1); for(int i = 0; i < graph.size(); i++) { if(graph[i].size() > 0 && status[i]==false) { dfs(i, status, graph, 1); if(flag == false) return false; } } return true; } };