Verkon kaksijakoisuus

-- http://repl.it/erT/1

local WHITE = nil
local RED = 0
local BLACK = 1

local function visit(M, color, lastcolor, i)
    local pickedcolor = (lastcolor+1) % 2
    if (color[i] == WHITE) then
        color[i] = pickedcolor
        for j = 1, #M do
            if (i ~= j and (M[i][j] == 1 or M[j][i] == 1)) then
                if (not visit(M, color, pickedcolor, j)) then
                    return false
                end
            end
        end
    elseif (color[i] ~= pickedcolor) then
        return false
    end
    return true
end

local function cantwocolor(M)
    local color = {}
    for i = 1, #M do
        if (color[i] == WHITE) then
            if (not visit(M, color, 0, i)) then
                return false
            end
        end
    end
    return true
end

local M1 = {
    {0,1,0,0},
    {0,0,1,0},
    {0,0,0,1},
    {1,0,0,0},
}
local M2 = {
    {0,1,0},
    {0,0,1},
    {1,0,0},
}
local M3 = {
    {0,1,1,0,0,0},
    {1,0,0,1,0,0},
    {0,0,0,0,0,1},
    {0,0,0,0,0,0},
    {1,0,1,0,0,0},
    {0,0,0,0,0,0},
}
local M4 = {
    {0,1,1,0,0,0,0},
    {1,0,0,1,0,0,0},
    {0,0,0,0,0,1,0},
    {0,0,0,0,0,0,0},
    {1,0,0,0,0,0,1},
    {0,0,0,0,0,0,0},
    {0,0,1,0,0,0,0},
}

print(cantwocolor(M1), "expected", true)
print(cantwocolor(M2), "expected", false)
print(cantwocolor(M3), "expected", false)
print(cantwocolor(M4), "expected", true)