886.可能的二分法 | 785.判断二分图

785.判断二分图

存在一个 无向图 ，图中有 n 个节点。其中每个节点都有一个介于 0 到 n - 1 之间的唯一编号。给你一个二维数组 graph ，其中 graph[u] 是一个节点数组，由节点 u 的邻接节点组成。形式上，对于 graph[u] 中的每个 v ，都存在一条位于节点 u 和节点 v 之间的无向边。该无向图同时具有以下属性：
不存在自环（graph[u] 不包含 u）。
不存在平行边（graph[u] 不包含重复值）。
如果 v 在 graph[u] 内，那么 u 也应该在 graph[v] 内（该图是无向图）
这个图可能不是连通图，也就是说两个节点 u 和 v 之间可能不存在一条连通彼此的路径。
二分图 定义：如果能将一个图的节点集合分割成两个独立的子集 A 和 B ，并使图中的每一条边的两个节点一个来自 A 集合，一个来自 B 集合，就将这个图称为 二分图 。

如果图是二分图，返回 true ；否则，返回 false 。

示例 1：

输入：graph = [[1,2,3],[0,2],[0,1,3],[0,2]]
输出：false
解释：不能将节点分割成两个独立的子集，以使每条边都连通一个子集中的一个节点与另一个子集中的一个节点。

思路：（双色问题）遍历一遍图，一边遍历一边染色，看看能不能用两种颜色给所有节点染色，且相邻节点的颜色都不相同。 

class Solution {
public:
    bool res=true;
    vector<bool> visited;
    vector<bool> color;
    bool isBipartite(vectorint>>& graph) 
    {
        color.resize(graph.size());
        visited.resize(graph.size());
        for(int i=0;isize();i++)
        {
            if(!visited[i])
            {
                traverse(graph,i);
            }
        }
        return res;
    }
    void traverse(vectorint>>& graph,int i)
    {
        if(visited[i])
        return ;
        visited[i]=true;
        for(int j:graph[i])
        {
            if(!visited[j])//如果i的相邻结点j没有被遍历过，那么就染上和j不同的颜色，继续遍历
            {
                color[j]=!color[i];
                traverse(graph,j);
            }
            else//如果j被遍历过了，那么就判断下它和i的颜色是否相同，如果相同，那么就不是二分图
            {
                if(color[j]==color[i])
                {
                    res=false;
                    return ;
                }
            }
        }
    }
};

 

 886.可能的二分法

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

给定整数 n 和数组 dislikes ，其中 dislikes[i] = [ai, bi] ，表示不允许将编号为 ai 和  bi的人归入同一组。当可以用这种方法将所有人分进两组时，返回 true；否则返回 false。

示例 1：

输入：n = 4, dislikes = [[1,2],[1,3],[2,4]]
输出：true
解释：group1 [1,4], group2 [2,3]

思路：把 dislikes 构造成一幅图(无向图，因为两人相互讨厌)，然后执行二分图的判定算法 

把每个人看做图中的节点，相互讨厌的关系看做图中的边，由 dislikes 数组就可以构成一幅图；又因为题目说互相讨厌的人不能放在同一组里，相当于图中的所有节点都要放进两个不同的组；那就回到了「双色问题」，如果能够用两种颜色着色所有节点，且相邻节点颜色都不同，那么按照颜色把这些节点分成两组就ok了。

class Solution {
public:
    bool res=true;
    vector<bool> visited;
    vector<bool> color;
    bool possibleBipartition(int n, vectorint>>& dislikes) 
    {
        color.resize(n);
        visited.resize(n);
        vectorint>> graph;
        graph.resize(n);
        for(vector<int> edge:dislikes)//建立无向图的邻接表
        {
            int from=edge[0]-1;
            int to=edge[1]-1;
            graph[from].push_back(to);
            graph[to].push_back(from);
        }
        for(int i=0;i//遍历图的每一个结点，执行二分图判定
        {
            if(!visited[i])
            {
                traverse(graph,i);
            }
        }
        return res;
    }
    void traverse(vectorint>>& graph,int i)
    {
        if(visited[i])
        return ;
        visited[i]=true;
        for(int j:graph[i])
        {
            if(!visited[j])//j是i的相邻结点且j没有被遍历过，就让j取i相反的颜色，继续遍历
            {
                color[j]=!color[i];
                traverse(graph,j);
            }
            else//j是i的相邻结点且j被遍历过了
            {
                if(color[j]==color[i])//判断j和i颜色是否相同，相同就不是二分图
                {
                    res=false;
                    return;
                }
            }
        }
    }
};