Graph Coloring

Table of Contents

• 785. Is Graph Bipartite? (Medium)
• 886. Possible Bipartition (Medium)
• 924. Minimize Malware Spread (Hard)

785. Is Graph Bipartite?

• LeetCode | LeetCode CH (Medium)

• Tags: depth first search, breadth first search, union find, graph

• Determine if a graph is bipartite.

How to group

	Uncolored	Color 1	Color 2	Operation
Method 1	-1	0	1	1 - color
Method 2	0	1	-1	-color

785. Is Graph Bipartite? - Python Solution

from collections import deque
from typing import List


# BFS
def isBipartiteBFS(graph: List[List[int]]) -> bool:
    n = len(graph)
    # -1: not colored; 0: blue; 1: red
    color = [-1 for _ in range(n)]

    def bfs(node):
        q = deque([node])
        color[node] = 0

        while q:
            cur = q.popleft()

            for neighbor in graph[cur]:
                if color[neighbor] == -1:
                    color[neighbor] = 1 - color[cur]
                    q.append(neighbor)
                elif color[neighbor] == color[cur]:
                    return False
        return True

    for i in range(n):
        if color[i] == -1:
            if not bfs(i):
                return False

    return True


# DFS
def isBipartiteDFS(graph: List[List[int]]) -> bool:
    n = len(graph)
    # -1: not colored; 0: blue; 1: red
    color = [-1] * n

    def dfs(node, c):
        color[node] = c
        for neighbor in graph[node]:
            if color[neighbor] == -1:
                if not dfs(neighbor, 1 - c):
                    return False
            elif color[neighbor] == c:
                return False
        return True

    for i in range(n):
        if color[i] == -1:
            if not dfs(i, 0):
                return False

    return True


# |------------|------- |---------|
# |  Approach  |  Time  |  Space  |
# |------------|--------|---------|
# |    BFS     | O(V+E) |  O(V)   |
# |    DFS     | O(V+E) |  O(V)   |
# |------------|--------|---------|


graph = [[1, 2, 3], [0, 2], [0, 1, 3], [0, 2]]
print(isBipartiteBFS(graph))  # False
print(isBipartiteDFS(graph))  # False

886. Possible Bipartition

• LeetCode | LeetCode CH (Medium)

• Tags: depth first search, breadth first search, union find, graph

• Determine if a graph can be divided into two groups such that no two nodes of the same group are connected.

886. Possible Bipartition - Python Solution

from collections import deque
from typing import List


# BFS
def possibleBipartitionBFS(n: int, dislikes: List[List[int]]) -> bool:
    group = {i: -1 for i in range(1, n + 1)}

    # Undirected graph
    graph = {i: [] for i in range(1, n + 1)}
    for i, j in dislikes:
        graph[i].append(j)
        graph[j].append(i)

    def bfs(person):
        q = deque([person])
        group[person] = 0

        while q:
            cur = q.popleft()

            for neighbor in graph[cur]:
                if group[neighbor] == -1:
                    group[neighbor] = 1 - group[cur]
                    q.append(neighbor)
                elif group[neighbor] == group[cur]:
                    return False
        return True

    for i in range(1, n + 1):
        if group[i] == -1:
            if not bfs(i):
                return False
    return True


# DFS
def possibleBipartitionDFS(n: int, dislikes: List[List[int]]) -> bool:
    group = {i: -1 for i in range(1, n + 1)}
    graph = {i: [] for i in range(1, n + 1)}
    for i, j in dislikes:
        graph[i].append(j)
        graph[j].append(i)

    def dfs(person, g):
        group[person] = g

        for neighbor in graph[person]:
            if group[neighbor] == -1:
                if not dfs(neighbor, 1 - g):
                    return False
            elif group[neighbor] == g:
                return False

        return True

    for i in range(1, n + 1):
        if group[i] == -1:
            if not dfs(i, 0):
                return False

    return True


# |------------|------- |---------|
# |  Approach  |  Time  |  Space  |
# |------------|--------|---------|
# |    BFS     | O(V+E) |  O(V+E) |
# |    DFS     | O(V+E) |  O(V+E) |
# |------------|--------|---------|


n = 4
dislikes = [[1, 2], [1, 3], [2, 4]]
print(possibleBipartitionBFS(n, dislikes))  # True
print(possibleBipartitionDFS(n, dislikes))  # True

924. Minimize Malware Spread

• LeetCode | LeetCode CH (Hard)

• Tags: array, hash table, depth first search, breadth first search, union find, graph

924. Minimize Malware Spread - Python Solution

from typing import List


# Coloring
def minMalwareSpread(graph: List[List[int]], initial: List[int]) -> int:
    n = len(graph)
    initial = set(initial)

    def dfs(x):
        visited.add(x)
        mark[x] = 1
        if x in initial:
            v.append(x)
        for nxt in range(n):
            if graph[x][nxt] and nxt != x and not mark[nxt]:
                dfs(nxt)

    ans = min(initial)
    mx = 0
    mark = [0] * n
    for i in range(n):
        if not mark[i]:
            visited = set()
            v = []
            dfs(i)
            if len(v) == 1 and (
                len(visited) > mx or len(visited) == mx and v[0] < ans
            ):
                ans, mx = v[0], len(visited)
    return ans


graph = [[1, 1, 0], [1, 1, 0], [0, 0, 1]]
initial = [0, 1]
print(minMalwareSpread(graph, initial))  # 0

Comments