886.可能的二分法

链接：886.可能的二分法
难度：Medium
标签：深度优先搜索、广度优先搜索、并查集、图
简介：给定整数 n  和数组 dislikes ，其中  dislikes[i] = [ai, bi] ，表示不允许将编号为 ai  和   bi 的人归入同一组。当可以用这种方法将所有人分进两组时，返回 true；否则返回 false。

题解 1 - cpp

• 编辑时间：2022-10-16
• 执行用时：220ms
• 内存消耗：62.7MB
• 编程语言：cpp
• 解法介绍：并查集，把所有人的对立连成一块，并不可能和当前值在同一个集。

struct UnionFind {
    vector<int> list;
    UnionFind(int n): list(vector<int>(n)) {
        for (int i = 0; i < n; i++) list[i] = i;
    }
    int find(int v) {
        return list[v] == v ? v : list[v] = find(list[v]);
    }
    void uni(int v1, int v2) {
        int p1 = find(v1), p2 = find(v2);
        if (p1 == p2) return;
        list[p1] = p2;
    }
    bool same(int v1, int v2) {
        return find(v1) == find(v2);
    }
};
class Solution {
public:
    bool possibleBipartition(int n, vector<vector<int>>& dislikes) {
        UnionFind uf(n + 1);
        vector<vector<int>> list(n + 1);
        for (auto &item : dislikes) {
            list[item[0]].push_back(item[1]);
            list[item[1]].push_back(item[0]);
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < list[i].size(); j++) {
                uf.uni(list[i][0], list[i][j]);
                if (uf.same(i, list[i][j])) return false;
            }
        }
        return true;
    }
};