785. Is Graph Bipartite?

leetcode medium

#array#csharp#graph#hash-table#leetcode#linked-list#medium#search#stack

Task

Есть неориентированный граф с n узлами, где каждый узел пронумерован от 0 до n - 1. Вам дан двумерный массив graph, где graph[u] — это массив узлов, смежных с узлом u. Более формально, для каждого v в graph[u] существует неориентированное ребро между узлом u и узлом v. Граф обладает следующими свойствами:

Нет петель (graph[u] не содержит u).

Нет параллельных ребер (graph[u] не содержит дублирующихся значений).

Если v есть в graph[u], то u есть в graph[v] (граф неориентированный).

Граф может быть несвязным, то есть могут существовать два узла u и v, между которыми нет пути.

Граф является двудольным, если узлы можно разделить на два независимых множества A и B так, что каждое ребро в графе соединяет узел из множества A с узлом из множества B.

Верните true, если и только если граф является двудольным.

Пример:

Input: graph = [[1,2,3],[0,2],[0,1,3],[0,2]]

Output: false

Explanation: There is no way to partition the nodes into two independent sets such that every edge connects a node in one and a node in the other.

C# solution

matched/original

public class Solution {
    public bool IsBipartite(int[][] graph) {
        Dictionary<int, int> color = new Dictionary<int, int>();
        for (int node = 0; node < graph.Length; node++) {
            if (!color.ContainsKey(node)) {
                Stack<int> stack = new Stack<int>();
                stack.Push(node);
                color[node] = 0;
                while (stack.Count > 0) {
                    int currentNode = stack.Pop();
                    foreach (int neighbor in graph[currentNode]) {
                        if (!color.ContainsKey(neighbor)) {
                            stack.Push(neighbor);
                            color[neighbor] = color[currentNode] ^ 1;
                        } else if (color[neighbor] == color[currentNode]) {
                            return false;
                        }
                    }
                }
            }
        }
        return true;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public bool IsBipartite(int[][] graph) {
        unordered_map<int, int> color = new unordered_map<int, int>();
        for (int node = 0; node < graph.size(); node++) {
            if (!color.count(node)) {
                stack<int> stack = new stack<int>();
                stack.push(node);
                color[node] = 0;
                while (stack.size() > 0) {
                    int currentNode = stack.pop();
                    foreach (int neighbor in graph[currentNode]) {
                        if (!color.count(neighbor)) {
                            stack.push(neighbor);
                            color[neighbor] = color[currentNode] ^ 1;
                        } else if (color[neighbor] == color[currentNode]) {
                            return false;
                        }
                    }
                }
            }
        }
        return true;
    }
}

Java solution

matched/original

class Solution {
    public boolean isBipartite(int[][] graph) {
        Map<Integer, Integer> color = new HashMap<>();
        for (int node = 0; node < graph.length; node++) {
            if (!color.containsKey(node)) {
                Stack<Integer> stack = new Stack<>();
                stack.push(node);
                color.put(node, 0);
                while (!stack.isEmpty()) {
                    int node = stack.pop();
                    for (int nei : graph[node]) {
                        if (!color.containsKey(nei)) {
                            stack.push(nei);
                            color.put(nei, color.get(node) ^ 1);
                        } else if (color.get(nei).equals(color.get(node))) {
                            return false;
                        }
                    }
                }
            }
        }
        return true;
    }
}

JavaScript solution

matched/original

class Solution {
    isBipartite(graph) {
        const color = {};
        for (let node = 0; node < graph.length; node++) {
            if (!(node in color)) {
                const stack = [node];
                color[node] = 0;
                while (stack.length > 0) {
                    const currentNode = stack.pop();
                    for (const neighbor of graph[currentNode]) {
                        if (!(neighbor in color)) {
                            stack.push(neighbor);
                            color[neighbor] = color[currentNode] ^ 1;
                        } else if (color[neighbor] === color[currentNode]) {
                            return false;
                        }
                    }
                }
            }
        }
        return true;
    }
}

Go solution

matched/original

func isBipartite(graph [][]int) bool {
    color := make(map[int]int)
    for node := 0; node < len(graph); node++ {
        if _, found := color[node]; !found {
            stack := []int{node}
            color[node] = 0
            for len(stack) > 0 {
                currentNode := stack[len(stack)-1]
                stack = stack[:len(stack)-1]
                for _, neighbor := range graph[currentNode] {
                    if _, found := color[neighbor]; !found {
                        stack = append(stack, neighbor)
                        color[neighbor] = color[currentNode] ^ 1
                    } else if color[neighbor] == color[currentNode] {
                        return false
                    }
                }
            }
        }
    }
    return true
}

Explanation

Algorithm

Мы будем хранить массив (или hashmap) для поиска цвета каждого узла: color[node]. Цвета могут быть 0, 1 или неокрашенные (-1 или null).

Мы должны быть внимательны к рассмотрению несвязных компонентов графа, выполняя поиск для каждого узла. Для каждого неокрашенного узла мы начнем процесс окрашивания, выполняя поиск в глубину (DFS) для этого узла. Каждый соседний узел получает цвет, противоположный цвету текущего узла. Если мы обнаруживаем, что соседний узел окрашен в тот же цвет, что и текущий узел, значит, наше окрашивание невозможно.

Для выполнения поиска в глубину мы используем стек. Для каждого неокрашенного соседа в graph[node] мы будем его окрашивать и добавлять в наш стек, который действует как своего рода "список дел" для узлов, которые нужно посетить дальше. Наш внешний цикл для start... гарантирует, что мы окрасим каждый узел.

😎