零，题目描述

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:

  1. Input: N = 4, dislikes = [[1,2],[1,3],[2,4]]
  2. Output: true
  3. Explanation: group1 [1,4], group2 [2,3]

Example 2:

Input: N = 3, dislikes = [[1,2],[1,3],[2,3]]
Output: false

Example 3:

Input: N = 5, dislikes = [[1,2],[2,3],[3,4],[4,5],[1,5]]
Output: false

Note:

  1. 1 <= N <= 2000
  2. 0 <= dislikes.length <= 10000
  3. 1 <= dislikes[i][j] <= N
  4. dislikes[i][0] < dislikes[i][1]
  5. There does not exist i != j for which dislikes[i] == dislikes[j].

一，题目分析

给定一组关系，a dislike b，那么a和b不能分在一组。问能不能把所有的人都分在两组之内
这个问题实际上可以转换为图问题[1,2]，就表示节点1和节点2可以连接在一起，说明是一条边。
把这样一幅图构建好，从一个节点开始设置为分组1，然后所有相邻的节点都设置为2，然后BFS/DFS就完事了。
这样一旦发现有相邻节点已经设置过分组了，且和自身节点的分组相同，则说明无法分为两组。就失败了，返回false。
如下例子。
因为2与3，4是相邻的，是不同分组的。但是4与3相邻，导致分组失败。

[[1,2],[2,4],[2,3],[3,4],[5,6]]

image.png

二，代码解析

（1）首先先从给定的边关系中构建一个邻接矩阵（也就是表示图的一种方法）
（2）创建一个分组表，group[n]表明节点n的分组（初始是0，表明没有分组，1表示分组1，2表示分组2）
（3）对每个没有遍历过的节点进行BFS遍历。设置相邻节点的分组，一旦发现有已经遍历过的邻居节点和自身分组相同就说明
分组失败了，返回false。
（4）BFS用Queue，DFS用Stack。

//
// Created by lidong on 2020/5/27.
//
#include <vector>
#include <queue>
using namespace std;

//TODO LeetCode 886
class PossibleBipartition_886
{
public:
    /**
     * 本质上就是一个图
     * @param N
     * @param dislikes
     * @return
     */
    bool possibleBipartition(int N, vector<vector<int>> &dislikes)
    {
        /*
         * Input: N = 5, dislikes = [[1,2],[2,3],[3,4],[4,5],[1,5]]
         * Output: false
         */
        if (N <= 2)
            return true;
        //先构建图
        vector<vector<int> > graph(N + 1);
        for (auto pair : dislikes)
        {
            graph[pair[0]].push_back(pair[1]);
            graph[pair[1]].push_back(pair[0]);
        }

        //分组vector
        vector<int> group(N + 1);
        //之所以for循环，是因为图不一定是联通的。可能有孤立节点存在
        for(int i = 1; i < group.size(); i++)
        {
            if(group[i] != 0)
                continue;
            group[i] = 1;
            queue<int> q;
            q.push(i);
            while (!q.empty())
            {
                int point = q.front();
                q.pop();
                for (auto neighbor : graph[point])
                {
                    if (group[neighbor] == 0)
                    {
                        group[neighbor] = 3 - group[point];
                        q.push(neighbor);
                    }
                    else if (group[neighbor] == group[point])
                        return false;
                }
            }
        }
        return true;
    }
};