785.Is Graph Bipartite?
Given an undirected? 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 another node in B. The graph is given in the following form:? Example 1: Input: [[1,3],[0,2],[1,2]] Output: true Explanation: The graph looks like this: 0----1 | | | | 3----2 We can divide the vertices into two groups: {0,2} and {1,3}. Example 2: Input: [[1,2,1,2]] Output: false Explanation: The graph looks like this: 0----1 | | | | 3----2 We cannot find a way to divide the set of nodes into two independent subsets. ? Note:
判断一个图是否是二分图。这题给出了二分图的定义:即图上的顶点可以被分为互相独立的两簇,图上每条的两个顶点分别在这两簇中。做法可以是模拟这个定义,对图上每条边的顶点进行着色。如果图上每条边的顶点都能不冲突的着上两个色。则可以是二分图,解法可以是BFS也可以是DFS,下面给出DFS的解法: class Solution(object): def isBipartite(self,graph): """ :type graph: List[List[int]] :rtype: bool """ colorset = [-1] * len(graph) 参考解法链接:https://leetcode.com/problems/is-graph-bipartite/discuss/115487/Java-Clean-DFS-solution-with-Explanation (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |
- Codeforces Hello 2019 F. Alex and a TV Show[bitset+莫比
- java-使用工厂方法的Spring autowire对象
- A Deep Learning-Based System for Vulnerability Detectio
- perl – 如何让DBD :: Pg可靠地超时?
- 介绍 Echoo: go 语言编写的 echo 服务器
- golang reflection
- Delphi-ADOQuery查询、插入、删除、修改
- delphi实现执勤表
- <<BASM 初学者入门>> 第 2 课
- Golang实现web api接口调用及web数据抓取[get post模式]