[Swift]LeetCode886.可能的二分法|PossibleBipartition

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

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

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

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

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

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

Given a set of N people (numbered 1, 2, ..., N), we would like to split everyone into two groups of any size.

Each person may dislike some other people, and they should not go into the same group.

Formally, if dislikes[i] = [a, b], it means it is not allowed to put the people numbered a and b into the same group.

Return true if and only if it is possible to split everyone into two groups in this way.

Example 1:

Input: N = [[1,2],[1,3],[2,4]]
Output: true
Explanation: group1 [1,4], group2 [2,3]

Example 2:

Input: N = [[1,2],[1,3],[2,3]]
Output: false

Example 3:

Input: N = [[1,2],[2,3],[3,4],[4,5],[1,5]]
Output: false

Note:

1 <= N <= 2000
0 <= dislikes.length <= 10000
1 <= dislikes[i][j] <= N
dislikes[i][0] < dislikes[i][1]
There does not exist i != j for which dislikes[i] == dislikes[j].

给定一组 N 人（编号为 1, 2, ..., N），我们想把每个人分进任意大小的两组。

每个人都可能不喜欢其他人，那么他们不应该属于同一组。

形式上，如果 dislikes[i] = [a, b]，表示不允许将编号为 a 和 b 的人归入同一组。

当可以用这种方法将每个人分进两组时，返回 true；否则返回 false。

示例 1：

输入：N = 4, dislikes = [[1,2],[1,3],[2,4]]
输出：true
解释：group1 [1,4], group2 [2,3]

示例 2：

输入：N = 3, dislikes = [[1,2],[1,3],[2,3]]
输出：false

示例 3：

输入：N = 5, dislikes = [[1,2],[2,3],[3,4],[4,5],[1,5]]
输出：false

提示：

1 <= N <= 2000
0 <= dislikes.length <= 10000
1 <= dislikes[i][j] <= N
dislikes[i][0] < dislikes[i][1]
对于 dislikes[i] == dislikes[j] 不存在 i != j

【BFS】

Runtime: 836 ms

Memory Usage: 19.8 MB

 1 class Solution {
 2     func possibleBipartition(_ N: Int, _ dislikes: [[Int]]) -> Bool {
 3         var len:Int = dislikes.count
 4         if len < 2 {return true}
 5         var color:[Int] = [Int](repeating:0,count:N + 1)
 6         var graph:[[Int]] = [[Int]](repeating:[Int](),count:N + 1)
 7         for i in 0..<len
 8         {
 9             var m:Int = dislikes[i][0]
10             var n:Int = dislikes[i][1]
11             graph[m].append(n)
12             graph[n].append(m)
13         }
14         for i in 1...N
15         {
16             if color[i] == 0
17             {
18                 color[i] = 1
19                 var q:[Int] = [Int]()
20                 q.append(i)
21                 while (!q.isEmpty)
22                 {
23                     var cur:Int = q.removeFirst()
24                     for j in graph[cur]
25                     {
26                         if color[j] == 0
27                         {
28                             color[j] = color[cur] == 1 ? 2 : 1
29                             q.append(j)
30                         }
31                         else
32                         {
33                             if color[j] == color[cur] {return false}
34                         }
35                     }
36                 }
37             }
38         }
39         return true
40     }
41 }

【DFS】

Runtime: 1560 ms

Memory Usage: 50.2 MB

 1 class Solution {
 2     func possibleBipartition(_ N: Int, _ dislikes: [[Int]]) -> Bool {
 3         var graph:[[Int]] = [[Int]](repeating:[Int](repeating:0,count:N),count:N)
 4         for d in dislikes
 5         {
 6             graph[d[0] - 1][d[1] - 1] = 1
 7             graph[d[1] - 1][d[0] - 1] = 1
 8         }
 9         var group:[Int] = [Int](repeating:0,count:N)
10         for i in 0..<N
11         {
12             if group[i] == 0 && !dfs(graph, &group, i, 1)
13             {
14                 return false
15             }
16         }
17         return true
18     }
19 
20     func dfs(_ graph:[[Int]],_ group:inout [Int],_ index:Int,_ g:Int) -> Bool
21     {
22         group[index] = g
23         for i in 0..<graph.count
24         {
25             if graph[index][i] == 1
26             {
27                 if group[i] == g
28                 {
29                     return false
30                 }
31                 if group[i] == 0 && !dfs(graph, &group, i, -g)
32                 {
33                     return false
34                 }
35             }
36         }
37         return true
38     }
39 }