题目描述

给出N个人的集合，我们想把他们分成任意大小的两个集合。

每个人可能会不喜欢某些人，因此我们不能把他们分入相同的组。

例如，如果dislikes[i] = [a, b]，说明我们不能把a和b两个人放进相同的组。判断我们是否能找到满足条件的分组方式，当且仅当能找到这样的分组方式时返回true.

样例

输入: N = 4, dislikes = [[1,2],[1,3],[2,4]]
输出: true
说明: group1 [1,4], group2 [2,3]

算法1

(dfs) $O(M)$

即经典的二部图判定问题，可以用染色法进行判断。互相不喜欢的两个人之间连上一条边，边连接的两个顶点染上不同的颜色。对图进行深搜，判断是否会出现冲突（即是否有边连接的顶点是同一种颜色）。可以用领接表来保存图减少存储空间。

时间复杂度分析：需要遍历图中的边，复杂度为$O(M)$，M为图的边数（即dislikes数组的大小）

C++ 代码

class Solution {
public:
    vector<vector<int>>graph;
    vector<int>color;
    bool dfs(int v, int N){
        for(int i = 0;i<graph[v].size();i++){
            int p = graph[v][i];
            if(color[p]==color[v])//冲突
                return false;
            if(color[p]==-1){
                color[p] = 1-color[v];
                bool res = dfs(p, N);
                if(!res)
                    return false;
            }
        }
        return true;
    }
    bool possibleBipartition(int N, vector<vector<int>>& dislikes) {
        for(int i = 0;i<=N;i++){
            color.push_back(-1);
            vector<int>tmp;
            graph.push_back(tmp);
        }
        for(int i= 0;i<dislikes.size();i++){//建图 graph[v]记录的是与v连通的结点
            graph[dislikes[i][0]].push_back(dislikes[i][1]);
            graph[dislikes[i][1]].push_back(dislikes[i][0]);
        }
        if(dislikes.size()==0)
            return true;
        for(int i = 1;i<N;i++){
            if(color[i]==-1){
                color[i] = 0;
                bool res = dfs(i, N);
                if(!res)
                    return false;
            }
        }
        return true;
    }
};