886. Possible Bipartition

[Tcdian]

886. Possible Bipartition

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

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

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

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

Example 1

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

Example 2

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

Example 3

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

Note

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

[Tcdian]

Solution

• JavaScript Solution

/**
 * @param {number} N
 * @param {number[][]} dislikes
 * @return {boolean}
 */
var possibleBipartition = function(N, dislikes) {
    const graph = Array.from(new Array(N + 1), () => []);
    for (let i = 0; i < dislikes.length; i++) {
        const [a, b] = dislikes[i];
        graph[a].push(b);
        graph[b].push(a);
    }
    // 0 未分组，1 分组1，-1 分组2
    const grouped = new Array(N + 1).fill(0);
    for (let i = 1; i <= N; i++) {
        if (grouped[i] === 0 && !dfs(i, 1)) {
            return false;
        }
    }
    return true;

    function dfs(people, group) {
        if (grouped[people] !== 0) {
            return grouped[people] === group;
        }
        grouped[people] = group;
        const dislikePeoples = graph[people];
        for (let i = 0; i < dislikePeoples.length; i++) {
            if (!dfs(dislikePeoples[i], -group)) {
                return false;
            } 
        }
        return true;
    }
};

• TypeScript Solution

var possibleBipartition = function(N: number, dislikes: number[][]): boolean {
    const graph: number[][] = Array.from(new Array(N + 1), () => []);
    for (let i = 0; i < dislikes.length; i++) {
        const [a, b] = dislikes[i];
        graph[a].push(b);
        graph[b].push(a);
    }
    // 0 未分组，1 分组1，-1 分组2
    const grouped = new Array(N + 1).fill(0);
    for (let i = 1; i <= N; i++) {
        if (grouped[i] === 0 && !dfs(i, 1)) {
            return false;
        }
    }
    return true;

    function dfs(people: number, group: number): boolean {
        if (grouped[people] !== 0) {
            return grouped[people] === group;
        }
        grouped[people] = group;
        const dislikePeoples = graph[people];
        for (let i = 0; i < dislikePeoples.length; i++) {
            if (!dfs(dislikePeoples[i], -group)) {
                return false;
            } 
        }
        return true;
    }
};