赞
踩
题目来源:https://leetcode.cn/problems/possible-bipartition/
大致题意:
给一个整数 n,表示当前有 n 个人,他们的编号是 1 ~ n。再给一个二维数组,其中每个一维数组有两个元素,表示编号为第一个元素的人不喜欢编号为第二个元素的人
如果两个人不喜欢,那么就不能放在一个分组里,求 n 个人能否放在两个分组里
每一个不喜欢的关系都可以看作一条边,那么所有关系和所有的人就组成了一张图
既然每条边都是不喜欢,那么边相连的两个顶点就需要在不同分组
于是可以使用一个数组表示每个节点对应的分组,然后对图进行遍历,遍历过程中需要判断当前相连节点之间的分组情况:
遍历时,若对应节点未分组,则以其为起点进行遍历,遍历过程中根据节点之间的关系进行判断和染色
解题步骤为:
代码:
public boolean possibleBipartition(int n, int[][] dislikes) { int[] color = new int[n + 1]; // 存节点对应的分组 List<Integer>[] edges = new List[n + 1]; // 存图 for (int i = 0; i <= n; i++) { edges[i] = new ArrayList<>(); } // 建图 for (int[] relation : dislikes) { edges[relation[0]].add(relation[1]); edges[relation[1]].add(relation[0]); } // 遍历所有节点 for (int i = 1; i <= n; i++) { // 若对应节点未分组 if (color[i] == 0) { // 以其为起点进行 BFS 遍历 Queue<Integer> queue = new ArrayDeque<>(); queue.add(i); // 标记当前节点应该在的分组 boolean flag = false; while (!queue.isEmpty()) { // 根据标志位表示当前分组值 int temp = flag ? 1 : -1; int size = queue.size(); // 取出当前步骤所有节点,并判断是否有分组冲突 for (int j = 0; j < size; j++) { int cur = queue.poll(); // 当前节点分组 color[cur] = temp; // 判断当前节点相连节点 for (int next : edges[cur]) { // 如果未分组,加入队列 if (color[next] == 0) { queue.add(next); } else { // 如果已分组,判断是否冲突 if (color[next] == temp) { return false; } } } } // 更新标志位 flag = !flag; } } } return true; }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。