加入收藏 | 设为首页 | 会员中心 | 我要投稿 李大同 (https://www.lidatong.com.cn/)- 科技、建站、经验、云计算、5G、大数据,站长网!
当前位置: 首页 > 大数据 > 正文

LeetCode 785. Is Graph Bipartite?

发布时间:2020-12-14 05:14:36 所属栏目:大数据 来源:网络整理
导读:Given an undirected graph, return true if and only if it is bipartite.Recall that a graph is bipartite if we can split it ‘ s set of nodes into two independent subsets A and B such that every edge in the graph has one node in A and anothe
Given an undirected graph,return true if and only if it is bipartite.
Recall that a graph is bipartite if we can split its set of nodes into two independent subsets A and B such that every edge in the graph has one node in A and another node in B.
The graph is given in the following form: graph[i] is a list of indexes j for which the edge between nodes i and j exists.  Each node is an integer between 0 and graph.length - 1.  There are no self edges or parallel edges: graph[i] does not contain i,and it doesnt contain any element twice.

判断二分图,二分图染色的基本做法,DFS加染色

 1 class Solution {
 2 public:
 3     int c=1;
 4     int color[110]={0};
 5     bool isBipartite(vector<vector<int>>& graph) {
 6         for(int i=0; i<graph.size(); i++){
 7             if(color[i]==0){
 8                 if(!DFS(i,c,graph)){
 9                     return false;
10                 }
11             }
12         }
13         return true;
14     }
15     bool DFS(int v,int c,vector<vector<int>>& graph){
16         color[v]=c;
17         for(int i=0; i<graph[v].size(); i++){
18             if(color[graph[v][i]]==c)
19                 return false;
20             if(color[graph[v][i]]==0&&!DFS(graph[v][i],-c,graph))
21                 return false;
22         }
23         return true;
24     }
25 };

(编辑:李大同)

【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容!

    推荐文章
      热点阅读