given a formula in conjunctive normal form 2cnf finds a way to assign truefalse values to all variables to satisfy all clauses or reports there is no solution https en wikipedia orgwiki2satisfiability format each clause is a pair of literals each literal in the form name isneg where name is an arbitrary identifier and isneg is true if the literal is negated perform a depth first search traversal of the graph starting at the given vertex stores the order in which nodes were visited to the list in transposed order perform a depth first search traversal of the graph starting at the given vertex records all visited nodes as being of a certain strongly connected component add a directed edge to the graph computes the strongly connected components of a graph order visited vertex false for vertex in graph graphtransposed vertex for vertex in graph for source neighbours in graph iteritems for target in neighbours addedgegraphtransposed target source for vertex in graph if not visitedvertex dfstransposedvertex graphtransposed order visited visited vertex false for vertex in graph vertexscc currentcomp 0 for vertex in reversedorder if not visitedvertex each dfs will visit exactly one component dfsvertex currentcomp vertexscc graph visited currentcomp 1 return vertexscc def buildgraphformula solves the 2sat problem entry point for testing perform a depth first search traversal of the graph starting at the given vertex stores the order in which nodes were visited to the list in transposed order perform a depth first search traversal of the graph starting at the given vertex records all visited nodes as being of a certain strongly connected component add a directed edge to the graph computes the strongly connected components of a graph each dfs will visit exactly one component builds the implication graph from the formula solves the 2 sat problem the formula is contradictory an arbitrary representant from each component true false value for each strongly connected component entry point for testing
def dfs_transposed(vertex, graph, order, visited):
    
    visited[vertex] = True

    for adjacent in graph[vertex]:
        if not visited[adjacent]:
            dfs_transposed(adjacent, graph, order, visited)

    order.append(vertex)


def dfs(vertex, current_comp, vertex_scc, graph, visited):
    
    visited[vertex] = True
    vertex_scc[vertex] = current_comp

    for adjacent in graph[vertex]:
        if not visited[adjacent]:
            dfs(adjacent, current_comp, vertex_scc, graph, visited)


def add_edge(graph, vertex_from, vertex_to):
    
    if vertex_from not in graph:
        graph[vertex_from] = []

    graph[vertex_from].append(vertex_to)


def scc(graph):
    
    order = []
    visited = {vertex: False for vertex in graph}

    graph_transposed = {vertex: [] for vertex in graph}

    for (source, neighbours) in graph.iteritems():
        for target in neighbours:
            add_edge(graph_transposed, target, source)

    for vertex in graph:
        if not visited[vertex]:
            dfs_transposed(vertex, graph_transposed, order, visited)

    visited = {vertex: False for vertex in graph}
    vertex_scc = {}

    current_comp = 0
    for vertex in reversed(order):
        if not visited[vertex]:
            
            dfs(vertex, current_comp, vertex_scc, graph, visited)
            current_comp += 1

    return vertex_scc


def build_graph(formula):
    
    graph = {}

    for clause in formula:
        for (lit, _) in clause:
            for neg in [False, True]:
                graph[(lit, neg)] = []

    for ((a_lit, a_neg), (b_lit, b_neg)) in formula:
        add_edge(graph, (a_lit, a_neg), (b_lit, not b_neg))
        add_edge(graph, (b_lit, b_neg), (a_lit, not a_neg))

    return graph


def solve_sat(formula):
    
    graph = build_graph(formula)
    vertex_scc = scc(graph)

    for (var, _) in graph:
        if vertex_scc[(var, False)] == vertex_scc[(var, True)]:
            return None  

    comp_repr = {}  

    for vertex in graph:
        if not vertex_scc[vertex] in comp_repr:
            comp_repr[vertex_scc[vertex]] = vertex

    comp_value = {}  
    components = sorted(vertex_scc.values())

    for comp in components:
        if comp not in comp_value:
            comp_value[comp] = False

            (lit, neg) = comp_repr[comp]
            comp_value[vertex_scc[(lit, not neg)]] = True

    value = {var: comp_value[vertex_scc[(var, False)]] for (var, _) in graph}

    return value


def main():
    
    formula = [(('x', False), ('y', False)),
               (('y', True), ('y', True)),
               (('a', False), ('b', False)),
               (('a', True), ('c', True)),
               (('c', False), ('b', True))]

    result = solve_sat(formula)

    for (variable, assign) in result.items():
        print(f"{variable}:{assign}")

if __name__ == '__main__':
    main()