[LeetCode] 886. Possible Bipartition 可能的二分图

时间  2019-11-06 标签 leetcode 886 possible bipartition 可能 二分 2分 图
 

Given a set of N people (numbered 1, 2, ..., N), we would like to split everyone into two groups of any size.html

Each person may dislike some other people, and they should not go into the same group. java

Formally, if dislikes[i] = [a, b], it means it is not allowed to put the people numbered a and b into the same group.git

Return true if and only if it is possible to split everyone into two groups in this way.github

  

Example 1:数组

Input: N = 4, dislikes = [[1,2],[1,3],[2,4]] Output: true 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:post

  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].

 

这道题又是关于二分图的题，第一次接触的时候是 Is Graph Bipartite?，那道题给的是建好的邻接链表（虽然是用数组实现的），可是本质上和这道题是同样的，同一条边上的两点是不能在同一个集合中的，那么这就至关于本题中的 dislike 的关系，也能够把每一个 dislike 看做是一条边，那么两端的两我的不能在同一个集合中。看透了题目的本质后，就不难作了，跟以前的题相比，这里惟一不一样的就是邻接链表没有给咱们建好，须要本身去建。不论是建邻接链表，仍是邻接矩阵都行，反正是要先把图建起来才能遍历。那么这里咱们先创建一个邻接矩阵好了，建一个大小为 (N+1) x (N+1) 的二维数组g，其中若 g[i][j] 为1，说明i和j互相不鸟。那么先根据 dislikes 的状况，把二维数组先赋上值，注意这里 g[i][j] 和 g[j][i] 都要更新，由于是互相不鸟，而并非某一方热脸贴冷屁股。下面就要开始遍历了，仍是使用染色法，使用一个一维的 colors 数组，大小为 N+1，初始化是0，因为只有两组，能够用1和 -1 来区分。那么开始遍历图中的结点，对于每一个遍历到的结点，若是其还未被染色，仍是一张白纸的时候，调用递归函数对其用颜色1进行尝试染色。在递归函数中，现将该结点染色，而后就要遍历全部跟其合不来的人，这里就发现邻接矩阵的好处了吧，否则每次还得遍历 dislikes 数组。因为这里是邻接矩阵，因此只有在其值为1的时候才处理，当找到一个跟其合不来的人，首先检测其染色状况，若是此时两我的颜色相同了，说明已经在一个组里了，这就矛盾了，直接返回 false。若是那我的仍是白纸一张，咱们尝试用相反的颜色去染他，若是没法成功染色，则返回 false。循环顺序退出后，返回 true，参见代码以下：

 

解法一：this

class Solution {
public:
    bool possibleBipartition(int N, vector<vector<int>>& dislikes) {
        vector<vector<int>> g(N + 1, vector<int>(N + 1));
        for (auto dislike : dislikes) {
            g[dislike[0]][dislike[1]] = 1;
            g[dislike[1]][dislike[0]] = 1;
        }
        vector<int> colors(N + 1);
        for (int i = 1; i <= N; ++i) {
            if (colors[i] == 0 && !helper(g, i, 1, colors)) return false;
        }
        return true;
    }
    bool helper(vector<vector<int>>& g, int cur, int color, vector<int>& colors) {
        colors[cur] = color;
        for (int i = 0; i < g.size(); ++i) {
            if (g[cur][i] == 1) {
                if (colors[i] == color) return false;
                if (colors[i] == 0 && !helper(g, i, -color, colors)) return false;
            }
        }
        return true;
    }
};

 

咱们还能够用迭代的写法，不实用递归函数，可是整个思路仍是彻底同样的。这里创建邻接链表，比邻接矩阵能省一些空间，只把跟其相邻的结点存入对应的数组内。仍是要创建一个一维 colors 数组，并开始遍历结点，若某个结点已经染过色了，跳过，不然就先给其染为1。而后借助 queue 来进行 BFS 遍历，现将当前结点排入队列，而后开始循环队列，取出队首结点，而后遍历其全部相邻结点，若是两个颜色相同，直接返回 false，不然若其为白纸，则赋相反颜色，而且排入队列。最终若顺序完成遍历，返回true，参见代码以下：

 

解法二： 
class Solution {
public:
    bool possibleBipartition(int N, vector<vector<int>>& dislikes) {
        vector<vector<int>> g(N + 1);
        for (auto dislike : dislikes) {
            g[dislike[0]].push_back(dislike[1]);
            g[dislike[1]].push_back(dislike[0]);
        }
        vector<int> colors(N + 1);
        for (int i = 1; i <= N; ++i) {
            if (colors[i] != 0) continue;
            colors[i] = 1;
            queue<int> q{{i}};
            while (!q.empty()) {
                int t = q.front(); q.pop();
                for (int cur : g[t]) {
                    if (colors[cur] == colors[t]) return false;
                    if (colors[cur] == 0) {
                        colors[cur] = -colors[t];
                        q.push(cur);
                    }
                }
            }
        }
        return true;
    }
};

 

其实这道题还可使用并查集 Union Find 来作，所谓的并查集，简单来讲，就是归类，将同一集合的元素放在一块儿。那么如何在能验证两个元素是否属于同一个集合呢，这里就要使用一个 root 数组（有时候是使用 HashMap），若是两个元素是同一个组的话，那么最终调用find函数返回的值应该是相同的，能够理解为老祖宗相同就是同一个组，两个点的 root 值不一样，也多是同一个组，由于 find 函数的运做机制是一直追根溯源到最原始的值。能够看到，这里博主的 find() 函数写的是递归形式，一行搞定碉堡了，固然也有 while 循环式的迭代写法。好，回过头来继续说这道题，这里仍是首先建图，这里创建邻接链表，跟上面的使用二维数组的方法不一样，这里使用来 HashMap，更加的节省空间。如今不须要用 colors 数组了，而是要使用并查集须要的 root 数组，给每一个点都初始化为不一样的值，由于在初始时将每一个点都看做一个不一样的组。而后开始遍历全部结点，若当前结点没有邻接结点，直接跳过。不然就要开始进行处理了，并查集方法的核心就两步，合并跟查询。咱们首先进行查询操做，对当前结点和其第一个邻接结点分别调用find函数，若是其返回值相同，则意味着其属于同一个集合了，这是不合题意的，直接返回 false。不然继续遍历其余的邻接结点，对于每个新的邻接结点，都调用 find() 函数，仍是判断若返回值跟原结点的相同，return false。不然就要进行合并操做了，根据敌人的敌人就是朋友的原则，全部的邻接结点之间应该属于同一个组，由于就两个组，我全部不爽的人都不能跟我在一个组，那么他们全部人只能都在另外一个组，因此须要将他们都合并起来，合并的时候不论是用 root[parent] = y 仍是 root[g[i][j]] = y 都是能够，由于无论直接跟某个结点合并，或者跟其祖宗合并，最终通过 find() 函数追踪溯源都会返回相同的值，参见代码以下：

 

解法三： 
class Solution {
public:
    bool possibleBipartition(int N, vector<vector<int>>& dislikes) {
        unordered_map<int, vector<int>> g;
        for (auto dislike : dislikes) {
            g[dislike[0]].push_back(dislike[1]);
            g[dislike[1]].push_back(dislike[0]);
        }
        vector<int> root(N + 1);
        for (int i = 1; i <= N; ++i) root[i] = i;
        for (int i = 1; i <= N; ++i) {
            if (!g.count(i)) continue;
            int x = find(root, i), y = find(root, g[i][0]);
            if (x == y) return false;
            for (int j = 1; j < g[i].size(); ++j) {
                int parent = find(root, g[i][j]);
                if (x == parent) return false;
                root[parent] = y;
            }
        }
        return true;
    }
    int find(vector<int>& root, int i) {
        return root[i] == i ? i : find(root, root[i]);
    }
};

 

讨论：能够看到本文中的三种解法在创建图的时候，使用的数据结构都不一样，解法一使用二维数组创建了邻接矩阵，解法二使用二维数组创建了邻接链表，解法三使用了 HashMap 创建了邻接链表。刻意使用不一样的方法就是为了你们能够对比区别一下，这三种方法都比较经常使用，在不一样的题目中选择最适合的方法便可。

 

Github 同步地址：url

 

相似题目：

 

参考资料：

https://leetcode.com/problems/possible-bipartition/

https://leetcode.com/problems/possible-bipartition/discuss/159085/java-graph

https://leetcode.com/problems/possible-bipartition/discuss/195303/Java-Union-Find

https://leetcode.com/problems/possible-bipartition/discuss/158957/Java-DFS-solution

 

LeetCode All in One 题目讲解汇总(持续更新中...)

联系我们 沪ICP备2021010478号-7