886. 可能的二分法#

1
给定一组 N 人（编号为 1, 2, ..., N）， 我们想把每个人分进任意大小的两组。
2

3
每个人都可能不喜欢其他人，那么他们不应该属于同一组。
4

5
形式上，如果 dislikes[i] = [a, b]，表示不允许将编号为 a 和 b 的人归入同一组。
6

7
当可以用这种方法将所有人分进两组时，返回 true；否则返回 false。
8

9

10

11
示例 1：
12

13
输入：N = 4, dislikes = [[1,2],[1,3],[2,4]]
14
输出：true
15
解释：group1 [1,4], group2 [2,3]
16
示例 2：
17

18
输入：N = 3, dislikes = [[1,2],[1,3],[2,3]]
19
输出：false
20
示例 3：
21

22
输入：N = 5, dislikes = [[1,2],[2,3],[3,4],[4,5],[1,5]]
23
输出：false
24

25

26
提示：
27

28
1 <= N <= 2000
29
0 <= dislikes.length <= 10000
30
dislikes[i].length == 2
31
1 <= dislikes[i][j] <= N
32
dislikes[i][0] < dislikes[i][1]
33
对于 dislikes[i] == dislikes[j] 不存在 i != j

1
class UnionFound {
2
public:
3
    vector<int> F;
4

5
    UnionFound(int n)
6
    {
7
        F = vector<int>(n, 0);
8
        for (int i = 0; i < n; i++)
9
        {
10
            F[i] = i;
11
        }
12
    }
13

14
    int Find(int x)
15
    {
16
        if (x == F[x]) return x;
17
        return F[x] = Find(F[x]);
18
    }
19

20
    void Union(int x, int y)
21
    {
22
        x = Find(x);
23
        y = Find(y);
24

25
        if (x != y) F[x] = y;
26
    }
27
};
28

29
class Solution {
30
public:
31
    bool possibleBipartition(int n, vector<vector<int> > &dislikes)
32
    {
33
        unordered_map<int, vector<int> > mp;
34

35
        for (int i = 0; i < dislikes.size(); i++) {
36
            mp[dislikes[i][0] - 1].push_back(dislikes[i][1] - 1);
37
            mp[dislikes[i][1] - 1].push_back(dislikes[i][0] - 1);
38
        }
39

40
        UnionFound uf(n);
41
        for (int i = 0; i < n; i++) {
42
            auto vec = mp[i];
43

44
            for (auto c : vec) {
45
                if (uf.Find(i) == uf.Find(c)) {
46
                    return false;
47
                }
48
                uf.Union(vec[0], c);
49
            }
50
        }
51
        return true;
52
    }
53
};