相互冲突的人能分进两组吗？先找出那条绕不回来的圈

"""Two teams or an odd cycle; standard-library teaching program."""
from collections import deque
from itertools import combinations, product
import json


def partition(n, edges):
    edges = tuple(edges)
    if type(n) is not int or not 0 <= n <= 1000:
        raise ValueError("n must be an integer in 0..1000")
    adjacency = [[] for _ in range(n)]
    for u, v in edges:
        if any(type(x) is not int or not 0 <= x < n for x in (u, v)):
            raise ValueError("unknown vertex")
        adjacency[u].append(v)
        adjacency[v].append(u)
    color, parent = [None] * n, [-1] * n
    for root in range(n):
        if color[root] is not None:
            continue
        color[root] = 0
        queue = deque([root])
        while queue:
            u = queue.popleft()
            for v in adjacency[u]:
                if color[v] is None:
                    color[v], parent[v] = 1 - color[u], u
                    queue.append(v)
                elif color[v] == color[u]:
                    a, b = [u], [v]
                    while parent[a[-1]] != -1:
                        a.append(parent[a[-1]])
                    while parent[b[-1]] != -1:
                        b.append(parent[b[-1]])
                    ancestors = set(a)
                    j = next(i for i, x in enumerate(b) if x in ancestors)
                    i = a.index(b[j])
                    cycle = a[:i + 1] + list(reversed(b[:j])) + [u]
                    return {"bipartite": False, "colors": None, "odd_cycle": cycle}
    return {"bipartite": True, "colors": color, "odd_cycle": None}


def exhaustive_coloring(n, edges):
    # Independent oracle: enumerate every assignment, no traversal or parent tree.
    if n > 6:
        raise ValueError("oracle limited to six vertices")
    return any(all(bits[u] != bits[v] for u, v in edges)
               for bits in product((0, 1), repeat=n))


def verify_witness(n, edges, result):
    if result["bipartite"]:
        colors = result["colors"]
        return len(colors) == n and all(colors[u] != colors[v] for u, v in edges)
    cycle = result["odd_cycle"]
    edge_set = {frozenset((u, v)) for u, v in edges}
    return (cycle[0] == cycle[-1] and (len(cycle) - 1) % 2 == 1
            and len(set(cycle[:-1])) == len(cycle) - 1
            and all(frozenset((u, v)) in edge_set for u, v in zip(cycle, cycle[1:])))


def main():
    checks = 0
    def check(ok):
        nonlocal checks
        if not ok:
            raise AssertionError("bipartite check failed")
        checks += 1

    graph_count = 0
    for n in range(6):
        possible = list(combinations(range(n), 2))
        for flags in product((0, 1), repeat=len(possible)):
            edges = [e for e, include in zip(possible, flags) if include]
            result = partition(n, edges)
            check(result["bipartite"] == exhaustive_coloring(n, edges))
            check(verify_witness(n, edges, result))
            graph_count += 1
    for n, edges in [(1, [(0, 0)]), (2, [(0, 1), (0, 1)]),
                     (4, [(0, 1), (1, 2), (2, 0)]), (4, [])]:
        result = partition(n, edges)
        check(result["bipartite"] == exhaustive_coloring(n, edges))
        check(verify_witness(n, edges, result))
    check(partition(3, iter([(0, 1), (1, 2)]))["bipartite"])
    for args in [(True, []), (-1, []), (2, [(0, 2)]), (2, [(False, 1)])]:
        try:
            partition(*args)
        except ValueError:
            check(True)
        else:
            raise AssertionError("invalid graph accepted")
    triangle = partition(3, [(0, 1), (1, 2), (2, 0)])
    square = partition(5, [(0, 1), (1, 2), (2, 3), (3, 0)])
    print(json.dumps({"checks_passed": checks, "exhaustive_graphs": graph_count,
                      "triangle": triangle, "square_plus_isolated": square,
                      "scope": "undirected graphs; two-color feasibility, not balanced teams or matching"}, indent=2))


if __name__ == "__main__":
    main()