幅優先探索 (BFS) の色塗りで、つながった 2 人を別の組に分けられるか調べる

from collections import deque


def two_teams(adj):
    team = [-1] * len(adj)
    for s in range(len(adj)):
        if team[s] != -1:
            continue
        ok = paint(adj, team, s)
        if not ok:
            return False
    return True


def paint(adj, team, s):
    # s から届く人を 0 と 1 で塗る
    team[s] = 0
    q = deque([s])
    while q:
        v = q.popleft()
        t = 1 - team[v]
        for u in adj[v]:
            if team[u] == -1:
                team[u] = t
                q.append(u)
            elif team[u] != t:
                return False
    return True

function twoTeams(adj) {
  const team = adj.map(
    () => -1);
  for (const s of team.keys()) {
    if (team[s] !== -1) {
      continue;
    }
    if (!paint(adj, team, s)) {
      return false;
    }
  }
  return true;
}

// s から届く人を 0 と 1 で塗る
function paint(adj, team, s) {
  team[s] = 0;
  const q = [s];
  for (const v of q) {
    const t = 1 - team[v];
    for (const u of adj[v]) {
      if (team[u] === t) {
        continue;
      }
      if (team[u] !== -1) {
        return false;
      }
      team[u] = t;
      q.push(u);
    }
  }
  return true;
}

func twoTeams(
	adj [][]int,
) bool {
	team := make([]int, len(adj))
	for i := range team {
		team[i] = -1
	}
	for s := range adj {
		if team[s] != -1 {
			continue
		}
		if !paint(adj, team, s) {
			return false
		}
	}
	return true
}

// s から届く人を 0 と 1 で塗る
func paint(
	adj [][]int,
	team []int, s int,
) bool {
	team[s] = 0
	q := []int{s}
	for i := 0; i < len(q); i++ {
		v := q[i]
		t := 1 - team[v]
		for _, u := range adj[v] {
			if team[u] == -1 {
				team[u] = t
				q = append(q, u)
			} else if team[u] != t {
				return false
			}
		}
	}
	return true
}