侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 471 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【图, DFS】可能的二分法

GabrielxD
2022-05-22 / 0 评论 / 0 点赞 / 51 阅读 / 1,286 字 / 正在检测是否收录...

题目

886. 可能的二分法


给定一组 n 人(编号为 1, 2, ..., n), 我们想把每个人分进任意大小的两组。每个人都可能不喜欢其他人,那么他们不应该属于同一组。

给定整数 n 和数组 dislikes ,其中 dislikes[i] = [ai, bi] ,表示不允许将编号为 aibi的人归入同一组。当可以用这种方法将所有人分进两组时,返回 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 <= 10^4
  • dislikes[i].length == 2
  • 1 <= dislikes[i][j] <= n
  • ai < bi
  • dislikes 中每一组都 不同

解题

方法一:DFS

思路

把人之间的不喜欢关系构建成一个无向图,顶点表示每个人,每条边表示两个顶点之间有不喜欢关系,不能分在同一组。使用邻接表(graph)(长度为n+1,索引为 0 的元素忽略)表示这个图,再创建一个映射表(vertexToGroup)存储每个顶点对应着它们被分到的组,其中只有两个组可供选择,0 表示一个组,1 又表示另一个组。

对于每个顶点,递归地将其它加入组(其中第一个元素可以加入任意一个组,对结果没有影响):

  • 如果当前顶点已经被分配了某组,则比较它「现在所在的组」和「由参数传进来它应该进的组(group)」是否相同,如果不同,则返回 false 表示该节点的归属出现了矛盾,不能用这种方法分组。否则返回 true 表示该节点的分组是正确的。
  • 如果顶点还未被分配组,就将其先分配到「由参数传进来它应该进的组」中,然后对遍历邻接表中该元素对应的集合,把所有和它不能进同一组的顶点全部递归地分配到其他组。如果分配的过程中出现矛盾,也返回 false。如果所有顶点都正常分配完则返回 true

代码

class Solution {
    private List<Integer>[] graph;
    private Map<Integer, Integer> vertexToGroup;

    public boolean possibleBipartition(int n, int[][] dislikes) {
        graph = (LinkedList<Integer>[]) new LinkedList[n + 1];
        for (int i = 1; i <= n; i++) graph[i] = new LinkedList<>();
        for (int[] dislike : dislikes) {
            graph[dislike[0]].add(dislike[1]);
            graph[dislike[1]].add(dislike[0]);
        }
        vertexToGroup = new HashMap<>();
        for (int i = 1; i <= n; i++) {
            if (!vertexToGroup.containsKey(i) && !dfs(i, 0)) return false;
        }
        return true;
    }

    private boolean dfs(int vertex, int group) {
        if (vertexToGroup.containsKey(vertex)) {
            return vertexToGroup.get(vertex) == group;
        }
        vertexToGroup.put(vertex, group);
        for (int dislike : graph[vertex]) {
            if (!dfs(dislike, group ^ 1)) return false;
        }
        return true;
    }
}

方法二:并查集

思路

我们知道对于 dislikes[i]=(a,b)dislikes[i] = (a, b) 而言,点 aa 和点 bb 必然位于不同的集合中,同时由于只有两个候选集合,因此这样的关系具有推断性:即对于 (a,b)(a, b)(b,c)(b, c) 可知 aacc 位于同一集合。

因此,我们可以对于每个点 xx 而言,建议一个反向点 x+nx + n:若点 xx 位于集合 AA 则其反向点 x+nx + n 位于集合 BB,反之同理。

基于此,我们可以使用「并查集」维护所有点的连通性:边维护边检查每个 dislikes[i]dislikes[i] 的联通关系,若 dislikes[i]=(a,b)dislikes[i] = (a, b) 联通,必然是其反向点联通所导致,必然是此前的其他 dislikes[j]dislikes[j] 导致的关系冲突,必然不能顺利划分成两个集合,返回 falsefalse,否则返回 truetrue

参考:【宫水三叶】判定二分图模板题 - 反向点+并查集

代码

class Solution {
    int[] root;

    void union(int p, int q) {
        root[find(p)] = find(q);
    }

    int find(int x) {
        return x == root[x] ? x : (root[x] = find(root[x]));
    }

    boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }

    public boolean possibleBipartition(int n, int[][] dislikes) {
        root = new int[n * 2 + 1];
        for (int i = 1; i <= n * 2; ++i) root[i] = i;
        for (int[] dislike : dislikes) {
            int a = dislike[0], b = dislike[1];
            if (isConnected(a, b)) return false;
            union(a, b + n);
            union(b, a + n);
        }
        return true;
    }
}

并查集模板:路径压缩优化的并查集

class Solution {
    public boolean possibleBipartition(int n, int[][] dislikes) {
        UnionFind uf = new UnionFind(n * 2 + 1);
        for (int[] dislike : dislikes) {
            int a = dislike[0], b = dislike[1];
            if (uf.isConnected(a, b)) return false;
            uf.union(a, b + n);
            uf.union(b, a + n);
        }
        return true;
    }

    static class UnionFind {
        private int[] root;

        public UnionFind() { }
        
        public UnionFind(int size) {
            root = new int[size];
            for (int i = 0; i < size; ++i) root[i] = i;
        }
        
        public int find(int n) {
            return n == root[n] ? n : (root[n] = find(root[n]));
        }

        public void union(int p, int q) {
            root[find(p)] = find(q);
        }

        public boolean isConnected(int p, int q) {
            return find(p) == find(q);
        }
    }

}
0

评论区