大佬教程收集整理的这篇文章主要介绍了886. Possible Bipartition，大佬教程大佬觉得挺不错的，现在分享给大家，也给大家做个参考。
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]
ConsTraints:
1 <= n <= 20000 <= dislikes.length <= 10000dislikes[i].length == 21 <= dislikes[i][j] <= ndislikes[i][0] < dislikes[i][1]i != j for which dislikes[i] == dislikes[j].class Solution { public Boolean possibleBipartition(int n, int[][] dis) { int[] visited = new int[n + 1]; List<Integer>[] graph = new ArrayList[n + 1]; for(int i = 0; i <= n; i++) graph[i] = new ArrayList(); for(int[] dislike: dis) { int fr = dislike[0], to = dislike[1]; graph[fr].add(to); graph[to].add(fr); } for(int i = 1; i <= n; i++) { if(visited[i] == 0 && graph[i].size() > 0) { visited[i] = 1; Queue<Integer> q = new LinkedList(); q.offer(i); while(!q.isEmpty()) { int cur = q.poll(); for(int j : graph[cur]) { if(visited[j] == 0) { visited[j] = (visited[cur] == 1 ? 2 : 1); q.offer(j); } else { if(visited[j] == visited[cur]) return false; } } } } } return true; } }
和785一样，但是得先建立graph，完了之后bfs涂色
class Solution { public Boolean possibleBipartition(int N, int[][] dislikes) { Map<Integer, List<Integer>> map = new HashMap(); for(int[] dis : dislikes) { map.computeIfAbsent(dis[0], a -> new ArrayList()).add(dis[1]); map.computeIfAbsent(dis[1], a -> new ArrayList()).add(dis[0]); } int[] color = new int[N + 1]; for(int i = 1; i <= N; i++) { if(color[i] == 0) { color[i] = 1; Queue<Integer> q = new LinkedList(); q.offer(i); while(!q.isEmpty()) { int cur = q.poll(); if(map.containsKey(cur)) { for(int nei : map.get(cur)) { if(color[nei] == 0){ color[nei] = color[cur] == 1 ? 2 : 1; q.offer(nei); } else { if(color[nei] == color[cur]) return false; } } } } } } return true; } }
以上是大佬教程为你收集整理的886. Possible Bipartition全部内容，希望文章能够帮你解决886. Possible Bipartition所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错，欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。