[Swift]LeetCode886. 可能的二分法 | Possible Bipartition_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. Fo

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...N15         {16             if color[i] == 017             {18                 color[i] = 119                 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] == 027                         {28                             color[j] = color[cur] == 1 ? 2 : 129                             q.append(j)30                         }31                         else32                         {33                             if color[j] == color[cur] {return false}34                         }35                     }36                 }37             }38         }39         return true40     }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..<N11         {12             if group[i] == 0 && !dfs(graph,&group,i,1)13             {14                 return false15             }16         }17         return true18     }19 20     func dfs(_ graph:[[Int]],_ group:inout [Int],_ index:Int,_ g:Int) -> Bool21     {22         group[index] = g23         for i in 0..<graph.count24         {25             if graph[index][i] == 126             {27                 if group[i] == g28                 {29                     return false30                 }31                 if group[i] == 0 && !dfs(graph,-g)32                 {33                     return false34                 }35             }36         }37         return true38     }39 }