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

发布时间：2020-12-14 04:58:34 所属栏目：百科来源：网络整理

导读：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

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 = 4,dislikes = [[1,2],[1,3],[2,4]] Output: true Explanation: group1 [1,4],group2 [2,3]

Example 2:

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

Example 3:

Input: N = 5,dislikes = [[1,[3,[4,5],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,N），?我们想把每个人分进任意大小的两组。

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

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

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

示例 1：

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

示例 2：

输入：N = 3,3]]
输出：false

示例 3：

输入：N = 5,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,-g)
32                 {
33                     return false
34                 }
35             }
36         }
37         return true
38     }
39 }

（编辑：李大同）

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