【Day 30 】2024-05-07 - 886. 可能的二分法

[azl397985856]

886. 可能的二分法

入选理由

暂无

题目地址

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

前置知识

• 图的遍历
• DFS

  题目描述

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

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

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

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

 

示例 1：

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

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

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

提示：

1 <= N <= 2000 0 <= dislikes.length <= 10000 dislikes[i].length == 2 1 <= dislikes[i][j] <= N dislikes[i][0] < dislikes[i][1] 对于dislikes[i] == dislikes[j] 不存在 i != j

[xil324]

class Solution(object):
    def possibleBipartition(self, n, dislikes):
        """
        :type n: int
        :type dislikes: List[List[int]]
        :rtype: bool
        """
        graph = {i: [] for i in range(n+1)}
        for a, b in dislikes:
            graph[a].append(b)
            graph[b].append(a)

        groups = [1] * (n+1)
        visited = set()
        self.res = True

        for i in range(1, n+1):
            if i not in visited:
                self.traverse(graph, i, visited, groups)
        return self.res

    def traverse(self, graph, position, visited, groups):
        if not self.res:
            return;
        visited.add(position)
        for neighbor in graph[position]:
            if neighbor not in visited:
                groups[neighbor] = -1 * groups[position]
                self.traverse(graph, neighbor,visited, groups)
            else:
                if groups[neighbor] == groups[position]:
                    self.res = False

Time complexity: O(V + E)

Space complexity: O(v^2)

[zhiyuanpeng]

class Solution:
    def dfs(self, g, i, c, colors):
        colors[i] = c
        # for it's connector v, try to color -1*c
        for j in g[i]:
            if colors[j] == c:
                return False
            elif colors[j] == 0 and not self.dfs(g, j, -1*c, colors):
                return False
        return True

    def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:
        g = collections.defaultdict(list)
        for x, y in dislikes:
            g[x-1].append(y-1)
            g[y-1].append(x-1)
        colors = [0] * n
        for i in range(n):
            if colors[i] == 0 and not self.dfs(g, i, 1, colors):
                return False
        return True

[Lizhao-Liu]

class Solution {
    func possibleBipartition(_ n: Int, _ dislikes: [[Int]]) -> Bool {
        var vertexMatrix = [[Int]](repeating: [Int](repeating: 0, count: n+1), count: n+1)

        for relation in dislikes {
            vertexMatrix[relation[0]][relation[1]] = 1
            vertexMatrix[relation[1]][relation[0]] = 1
        }

        var colors = [Int](repeating: 0, count: n+1)
        for i in 1...n {
            if  colors[i] == 0 && !dfs(vertexMatrix, &colors, i, 1){
                return false
            }
        }
        return true
    }

    func dfs(_ vertexMatrix: [[Int]], _ colors: inout [Int], _ curr : Int, _ color : Int) ->  Bool {
        colors[curr] = color
        for vertex in 1..<vertexMatrix[curr].count {
            if vertexMatrix[curr][vertex] == 1 {
                if colors[vertex] == color {
                    return false
                }
                if colors[vertex] == 0 && !dfs(vertexMatrix, &colors, vertex, -1 * color) {
                    return false
                }
            }
        }
        return true

    }
}

[lxy1108]

思路

维护两个集合，遍历dislikes数组，如果其中一个节点在其中一个集合里，那么另一个节点只能加入到另外一个集合里，若两个节点出现在相同集合里则发生冲突，

python3 代码

class Solution:
    def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:
        if not dislikes:
            return True
        edges = collections.defaultdict(list)
        for dislike in dislikes:
            edges[dislike[0]].append(dislike[1])
            edges[dislike[1]].append(dislike[0])
        queue = []
        set1 = set([dislikes[0][0]])
        set2 = set([dislikes[0][1]])
        queue = dislikes[1:]
        while queue:
            tmp = []
            s1,s2 = len(set1),len(set2)
            for a,b in queue:
                if a not in set1 and a not in set2 and b not in set1 and b not in set2:
                    tmp.append([a,b])
                else:
                    if a in set1:
                        if b in set1:
                            return False
                        set2.add(b)
                    elif a in set2:
                        if b in set2:
                            return False
                        set1.add(b)
            queue = tmp
            if len(set1)==s1 and len(set2)==s2 and queue:
                set1.add(queue[0][0])
                set2.add(queue[0][1])
                queue = queue[1:]
        return True

复杂度分析

空间和空间复杂度均为o(m+n) 其中m为dislikes数组的大小

[xy147]

js代码

const possibleBipartition = (N, dislikes) => {
  let graph = [...Array(N + 1)].map(() => Array()),
    colors = Array(N + 1).fill(-1);

  for (const d of dislikes) {
    graph[d[0]].push(d[1]);
    graph[d[1]].push(d[0]);
  }

  const dfs = (cur, color = 0) => {
    colors[cur] = color;
    for (const nxt of graph[cur]) {
      if (colors[nxt] !== -1 && colors[nxt] === color) return false;
      if (colors[nxt] === -1 && !dfs(nxt, color ^ 1)) return false;
    }
    return true;
  };

  for (let i = 0; i < N; ++i) if (colors[i] === -1 && !dfs(i, 0)) return false;

  return true;
};

复杂度分析

时间复杂度：O(n)

空间复杂度：O(n2)

[Martina001]

''' ''' class Solution { public boolean possibleBipartition(int n, int[][] dislikes) { // 巧了 早上刚学了并查集 先写一下看看UF // 这道题很明显是一个并查集的应用题 先处理一下dislikes数组，把dislikes[i][0]和dislikes[i][1]先union起来，再把同一个人的不喜欢的人数组遍历一遍，判断是否有connected UF myUf = new UF(n);

        // nums的value是List，存储索引对应的不喜欢的人,所以索引从1开始
        List<Integer>[] nums = new List[n + 1];
        // 别忘了初始化
        for (int i = 0; i <= n; ++i) {
            nums[i] = new ArrayList<Integer>();
        }
        for (int item[] : dislikes) {
            int a = item[0];
            int b = item[1];

            // 在a和b对应的list中添加对方
            nums[a].add(b);
            nums[b].add(a);
        }

        for (int i = 1; i <= n; i++) {
            List<Integer> list = nums[i];
            for (int j = 0; j < list.size(); j++) {
                // 连接在同一个数组中的人，注意连接是一体的，无需两两单独互相连接
                myUf.union(list.get(0), list.get(j));
                // 如果当前数组中的人和自己不喜欢的人（索引值）相连，就返回false
                if (myUf.connected(list.get(j), i)) {
                    return false;
                }

            }
        }
        return true;
    }

    class UF {
        private int count;
        private int parent[];

        public UF(int n) {
            parent = new int[n+1];
            for (int i = 0; i <= n; i++) {
                parent[i] = i;
            }
            count = n;
        }

        public int getUFCount() {
            return count;
        }

        public int findRoot(int x) {
            // 注意回溯的话要用if。循环的话要用while
           /* if (parent[x] != x) {
                parent[x] = findRoot(parent[x]);
            }
            return parent[x];*/
            while (parent[x] != x) {
                // 进行路径压缩
                parent[x] = parent[parent[x]];
                x = parent[x];
            }
            return x;
        }

        public void union(int a, int b) {
            int rootA = findRoot(a);
            int rootB = findRoot(b);
            if (rootA == rootB) {
                return;
            }
            parent[rootA] = rootB;

            // 别忘了count--
            count--;
        }

        public boolean connected(int a, int b) {
            return findRoot(a) == findRoot(b);
        }
    }
}

[wwz223]

/**
 * @param {number} n
 * @param {number[][]} dislikes
 * @return {boolean}
 */

var possibleBipartition = function(n, dislikes) {
    if(n==1){
        return true
    }
    dislikes= dislikes.sort((a,b)=>Math.min(a[0],a[1])-Math.min(b[0],b[1]))
    let list1=[],list2=[]
    for(let i = 0;i<dislikes.length;i++){
        let max =Math.max(dislikes[i][0],dislikes[i][1]),min =Math.min(dislikes[i][0],dislikes[i][1])
        let u1 = list1.indexOf(min)!=-1,u2 = list2.indexOf(min)!=-1
        if(u1||u2){
            if(u1){
                if(list1.indexOf(max)!=-1){
                    return false
                }
                list2.push(max)  

            }else
            if(u2){
                if(list2.indexOf(max)!=-1){
                    return false
                }
                list1.push(max) 
            }  
        }else list1=[min],list2=[max]

    }
    return true
};

[luzhaofeng]

class Solution:
    def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:
        def dfs(i, c):
            color[i] = c
            for j in g[i]:
                if color[j] == c:
                    return False
                if color[j] == 0 and not dfs(j, 3 - c):
                    return False
            return True

        g = defaultdict(list)
        color = [0] * n
        for a, b in dislikes:
            a, b = a - 1, b - 1
            g[a].append(b)
            g[b].append(a)
        return all(c or dfs(i, 1) for i, c in enumerate(color))

[GReyQT]

class Solution {
public:
    vector<vector<int>> g;
    unordered_map<int, int> color;
    bool dfs(int x, int c) {
        if (color.count(x)) {
            return color[x] == c;
        }
        color[x] = c;
        for (auto& e : g[x]) {
            if (false == dfs(e, -c)) {
                return false;
            }
        }
        return true;
    }
    bool possibleBipartition(int n, vector<vector<int>>& dislikes) {
        g.resize(n + 1);
        for (auto& e : dislikes) {
            int x = e[0];
            int y = e[1];
            g[x].push_back(y);
            g[y].push_back(x);
        }
        for (int i = 1; i < n; ++i) {
            if (!color.count(i)) {
                if (false == dfs(i, 1))
                    return false;
            }
        }
        return true;
    }
};

[Dtjk]

class Solution { public: int p[4010]; int find(int x) { if (p[x] != x) p[x] = find(p[x]); return p[x]; }

void union_(int i, int j) {
    p[find(i)] = p[find(j)];
}

bool connected(int i, int j) {
    return find(i) == find(j);
}
bool possibleBipartition(int n, vector<vector<int>>& dislikes) {
    for (int i = 1; i <= 2 * n; i++) p[i] = i;
    for (vector<int> dis : dislikes) {
        int a = dis[0], b = dis[1];
        if (connected(a, b)) return false;
        union_(a, b + n);
        union_(b, a + n);
    }
    return true;
}

};

[smallppgirl]

广度优先染色

class Solution:
    def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:
        g = [[] for _ in range(n)]
        for x, y in dislikes:
            g[x - 1].append(y - 1)
            g[y - 1].append(x - 1)
        color = [0] * n  # color[x] = 0 表示未访问节点 x
        for i, c in enumerate(color):
            if c == 0:
                q = deque([i])
                color[i] = 1
                while q:
                    x = q.popleft()
                    for y in g[x]:
                        if color[y] == color[x]:
                            return False
                        if color[y] == 0:
                            color[y] = -color[x]
                            q.append(y)
        return True

时间复杂 O(n+m) 空间复杂 O)m+n)

[Hermione666]

class Solution: def init(self): self.N = 2005 self.p = [i for i in range(2 * self.N)]

def find(self, x):
    if self.p[x] != x:
        self.p[x] = self.find(self.p[x])
    return self.p[x]

def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:
    for i in range(1, 2 * self.N):
        self.p[i] = i
    for d in dislikes:
        a, b = d[0], d[1]
        if self.find(a) == self.find(b):
            return False
        else:
            self.p[self.find(a)] = self.find(b + n)
            self.p[self.find(b)] = self.find(a + n)
    return True

[CathyShang]

思想

• 构建图
• 二分图 染色法
• dfs

class Solution {
    unordered_map<int, vector<int>> G;
    vector<int> _colors;
public:
    bool possibleBipartition(int n, vector<vector<int>>& dislikes) {
        for(auto& tmp:dislikes){
            int a = tmp[0]-1, b = tmp[1]-1;
            G[a].push_back(b);
            G[b].push_back(a);
        }
        _colors = vector<int> (n,0);
        for(int i = 0; i<n; ++i){
            if(_colors[i] == 0 && !dfs(i,1))
                return false;
        }
        return true;
    }
    bool dfs(int cur, int color){
        _colors[cur]=color;
        for(int next: G[cur]){
            if(_colors[next] == color) // 讨厌的已分组，结果是一组
                return false;
            if(_colors[next] == 0 && !dfs(next, -color)) // cur是color组，讨厌的未分组不是-color组（讨厌的不能是一组）
                return false;
        }
        return true;
    }
};

• Time $O(n+m)$ 人数n，关系数m
• Space $O(n+m)$