[Swift]LeetCode785.判断二分图|IsGraphBipartite?

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址： https://www.cnblogs.com/strengthen/p/10545335.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

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 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 doesn't contain any element twice.

Example 1:
Input: [[1,3], [0,2], [1,3], [0,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,3], [0,2], [0,1,3], [0,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:

graph will have length in range [1, 100].
graph[i] will contain integers in range [0, graph.length - 1].
graph[i] will not contain i or duplicate values.
The graph is undirected: if any element j is in graph[i], then i will be in graph[j].

给定一个无向图graph，当这个图为二分图时返回true。

如果我们能将一个图的节点集合分割成两个独立的子集A和B，并使图中的每一条边的两个节点一个来自A集合，一个来自B集合，我们就将这个图称为二分图。

graph将会以邻接表方式给出，graph[i]表示图中与节点i相连的所有节点。每个节点都是一个在0到graph.length-1之间的整数。这图中没有自环和平行边： graph[i] 中不存在i，并且graph[i]中没有重复的值。

示例 1:
输入: [[1,3], [0,2], [1,3], [0,2]]
输出: true
解释: 
无向图如下:
0----1
|    |
|    |
3----2
我们可以将节点分成两组: {0, 2} 和 {1, 3}。


示例 2:
输入: [[1,2,3], [0,2], [0,1,3], [0,2]]
输出: false
解释: 
无向图如下:
0----1
| \  |
|  \ |
3----2
我们不能将节点分割成两个独立的子集。

注意:

graph 的长度范围为 [1, 100]。
graph[i] 中的元素的范围为 [0, graph.length - 1]。
graph[i] 不会包含 i 或者有重复的值。
图是无向的: 如果j 在 graph[i]里边, 那么 i 也会在 graph[j]里边。

Runtime: 176 ms

Memory Usage: 19.2 MB

 1 class Solution {
 2     func isBipartite(_ graph: [[Int]]) -> Bool {
 3         var colors:[Int] = [Int](repeating:0,count:graph.count)
 4         for i in 0..<graph.count
 5         {
 6             if colors[i] != 0 {continue}
 7             colors[i] = 1
 8             var q:[Int] = [i]
 9             while(!q.isEmpty)
10             {
11                 var t:Int = q.first!
12                 q.removeFirst()
13                 for a in graph[t]
14                 {
15                     if colors[a] == colors[t] {return false}
16                     if colors[a] == 0
17                     {
18                         colors[a] = -1 * colors[t]
19                         q.append(a)
20                     }
21                 }                
22             }
23         }
24         return true
25     }
26 }

208ms

 1 class Solution {
 2     func isBipartite(_ graph: [[Int]]) -> Bool {
 3         let V = graph.count
 4         var colors = Array(repeating: -1, count: V)
 5         for i in 0 ..< V {
 6             if colors[i] == -1 && !validColor(&colors, 0, graph, i) {
 7                 return false
 8             }
 9         }
10         return true
11     }
12     
13     func validColor(_ colors: inout [Int], _ color: Int, _ graph: [[Int]], _ vertex: Int) -> Bool {
14         if colors[vertex] != -1 {
15             return colors[vertex] == color
16         }
17         colors[vertex] = color
18         for neighbor in graph[vertex] {
19             if !validColor(&colors, 1 - color, graph, neighbor) {
20                 return false
21             }
22         }
23         return true
24     }
25 }

212ms

 1 class Solution {
 2     func isBipartite(_ graph: [[Int]]) -> Bool {
 3     var color = Array<Color>(repeating: .unknown, count: graph.count)
 4     
 5     for i in 0..<graph.count {
 6         guard color[i] == .unknown else { continue }
 7         if !dfs(i: i, color: &color, graph: graph, paint: .red) { return false }
 8     }
 9         return true
10     }
11     func dfs(i: Int, color: inout [Color], graph: [[Int]], paint: Color) -> Bool {
12         guard color[i] == .unknown else {
13             return color[i] == paint
14         }
15         color[i] = paint
16         for neighbour in graph[i] {
17             if !dfs(i: neighbour, color: &color, graph: graph, paint: paint.opposite)
18             {
19                 return false 
20             }
21     }
22     return true
23   }
24 }
25 
26 enum Color {
27     case red
28     case blue
29     case unknown
30     
31     var opposite: Color {
32         switch self {
33         case .red:
34             return .blue
35         case .blue:
36             return .red
37         case .unknown:
38             return .unknown
39         }
40     }
41 }

220ms

 1 class Solution {
 2     func isBipartite(_ graph: [[Int]]) -> Bool {
 3         var visited: Set<Int> = []
 4         
 5         for seed in 0..<graph.count {
 6             if visited.contains(seed) { continue }
 7             
 8             var oddSet: Set<Int> = []
 9             var evenSet: Set<Int> = []
10             
11             var queue = [seed]
12             var level = 0
13             
14             while !queue.isEmpty {
15                 var nextLevel = [Int]()
16                 
17                 for vertex in queue {
18                     visited.insert(vertex)
19                     if level % 2 == 0 {      
20                         if oddSet.contains(vertex) {
21                             return false
22                         }
23 
24                         if !evenSet.contains(vertex) {
25                             nextLevel += graph[vertex]
26                             evenSet.insert(vertex)
27                         }
28                     } else {
29                         if evenSet.contains(vertex) {
30                             return false
31                         }
32 
33                         if !oddSet.contains(vertex) {
34                             nextLevel += graph[vertex]
35                             oddSet.insert(vertex)
36                         } 
37                     }
38                 }
39                 queue = nextLevel
40                 level += 1
41             }            
42         }        
43         return true
44     }
45 }

224ms

 1 class Solution {
 2     enum NodeStatus {
 3         case red, black, undefined
 4         func negate() -> NodeStatus {
 5             switch self {
 6                 case .red:
 7                     return .black
 8                 case .black:
 9                     return .red
10                 case .undefined:
11                     return .undefined
12             }
13         }
14     }
15     
16     var nodeStatus: [Int: NodeStatus] = [:]
17     var graph: [[Int]] = []
18     var nodeCount = 0
19     
20     func status(_ node: Int) -> NodeStatus {
21         return nodeStatus[node] ?? .undefined
22     }
23     
24     func findConflict(byFlooding nodes: [Int]) -> Bool {
25         var nextNodes = nodes
26         while nextNodes.count > 0 {
27             let currentNodes = nextNodes
28             nextNodes = [Int]()
29             for node in currentNodes {
30                 for adjacent in graph[node] {
31                     let currentStatus = status(node)
32                     let statusToColor = currentStatus.negate()
33                     if nodeStatus[adjacent] == .undefined {
34                         nodeStatus[adjacent] = statusToColor
35                         nextNodes.append(adjacent)
36                     } else if nodeStatus[adjacent] == currentStatus {
37                         return true
38                     }
39                 }
40             }
41         }
42         return false
43     }
44     
45     func undefinedNode() -> Int? {
46         for i in 0..<nodeCount {
47             if status(i) == .undefined {
48                 return i
49             }
50         }
51         return nil
52     }
53     
54     func setup(_ graph: [[Int]]) {
55         self.graph = graph
56         nodeCount = graph.count
57         for i in 0..<graph.count {
58             nodeStatus[i] = .undefined
59         }
60     }
61                
62     func isBipartite(_ graph: [[Int]]) -> Bool {
63         setup(graph)
64         while let node = undefinedNode() {
65             nodeStatus[node] = .red
66             let hasConflict = findConflict(byFlooding: [node])
67             if hasConflict {
68                 return false
69             }
70         }
71         
72         return true
73     }
74 }

228ms

 1 class Solution {
 2     func isBipartite(_ graph: [[Int]]) -> Bool {
 3         guard graph.count > 0 else {
 4             return false
 5         }
 6         let black = 0
 7         let white = 1
 8         var visited = [Int:Int]()
 9         
10         func bfs(node:Int, pColor:Int) -> Bool {
11             if let color = visited[node] {
12                 return color != pColor
13             }
14             
15             visited[node] = pColor == white ? black : white
16             
17             let neighb = graph[node]            
18             for n in neighb {
19                 if !bfs(node:n, pColor:visited[node]!) {
20                     return false 
21                 }
22             }
23             return true
24         }
25         
26         for i in 0..<graph.count {
27             if visited[i] == nil {
28                 if !bfs(node:i, pColor:white) {
29                     return false
30                 }
31             }    
32         }
33         
34         return true
35     }
36 }