"""
p67 — Is Graph Bipartite? (LeetCode 785, MEDIUM).

Bipartite <=> 2-colorable <=> no odd cycle (Konig's theorem).
BFS / DFS color propagation. Must visit every component.
"""
from __future__ import annotations
import itertools
import random
from collections import deque
from typing import List


def is_bipartite_bfs(graph: List[List[int]]) -> bool:
    n = len(graph)
    color = [-1] * n   # -1 = uncolored, 0 / 1 = the two sides
    for start in range(n):
        if color[start] != -1:
            continue
        color[start] = 0
        q = deque([start])
        while q:
            u = q.popleft()
            for v in graph[u]:
                if color[v] == -1:
                    color[v] = 1 - color[u]
                    q.append(v)
                elif color[v] == color[u]:
                    return False
    return True


def is_bipartite_dfs(graph: List[List[int]]) -> bool:
    n = len(graph)
    color = [-1] * n
    for start in range(n):
        if color[start] != -1:
            continue
        color[start] = 0
        stack = [start]
        while stack:
            u = stack.pop()
            for v in graph[u]:
                if color[v] == -1:
                    color[v] = 1 - color[u]
                    stack.append(v)
                elif color[v] == color[u]:
                    return False
    return True


def is_bipartite_brute(graph: List[List[int]]) -> bool:
    n = len(graph)
    if n == 0:
        return True
    # Try every 2-coloring.
    for assignment in itertools.product((0, 1), repeat=n):
        ok = True
        for u in range(n):
            for v in graph[u]:
                if assignment[u] == assignment[v]:
                    ok = False
                    break
            if not ok:
                break
        if ok:
            return True
    return False


def edge_cases() -> None:
    assert is_bipartite_bfs([[1, 3], [0, 2], [1, 3], [0, 2]]) is True   # 4-cycle
    assert is_bipartite_bfs([[1, 2, 3], [0, 2], [0, 1, 3], [0, 2]]) is False   # triangle
    assert is_bipartite_bfs([]) is True
    assert is_bipartite_bfs([[]]) is True   # single node
    assert is_bipartite_bfs([[1], [0]]) is True   # single edge
    # Disconnected: component 1 bipartite, component 2 has triangle
    assert is_bipartite_bfs([[1], [0], [3, 4], [2, 4], [2, 3]]) is False
    # Disconnected: both bipartite
    assert is_bipartite_bfs([[1], [0], [3], [2]]) is True
    print("edge_cases: PASS")


def _random_graph(n: int, rng: random.Random) -> List[List[int]]:
    adj: List[List[int]] = [[] for _ in range(n)]
    seen = set()
    edges = rng.randint(0, n * (n - 1) // 2)
    for _ in range(edges):
        u = rng.randrange(n)
        v = rng.randrange(n)
        if u == v:
            continue
        key = (min(u, v), max(u, v))
        if key in seen:
            continue
        seen.add(key)
        adj[u].append(v)
        adj[v].append(u)
    return adj


def stress_test() -> None:
    rng = random.Random(42)
    for trial in range(500):
        n = rng.randint(0, 8)
        g = _random_graph(n, rng)
        a = is_bipartite_bfs(g)
        b = is_bipartite_dfs(g)
        c = is_bipartite_brute(g)
        assert a == b == c, f"trial {trial}: g={g} bfs={a} dfs={b} brute={c}"
    print("stress_test: 500 trials — BFS, DFS, brute 2^n all agree.")


if __name__ == "__main__":
    edge_cases()
    stress_test()
    print("ALL TESTS PASSED")