Can We Split Into Two Teams?

Decide whether people can be assigned to two teams so that each listed pair is on opposite teams.

배우게 될 내용

사람과 갈등을 그래프로 모델링하기
두 색으로 이분 그래프인지 확인하기
그래프의 연결되지 않은 부분 처리하기

문제

Decide whether people can be assigned to two teams so that each listed pair is on opposite teams. Every person receives exactly one team; either team may be empty. People without a listed pair can go on either team. Check every connected group of constraints.

Implement split_into_two_teams(people, pairs).

Input

people: The number of people, numbered from 1.

pairs: Rows [first_person, second_person] that must be separated.

Output

Return true if any valid assignment exists, otherwise false. Do not return the assignment.

제약 조건

1 ≤ people ≤ 100,000. 0…200,000 pairs of distinct person IDs in 1…people. Duplicate pairs are allowed and repeat the same constraint.

예시

예시 1

입력:
pairs = [
    [1, 2],
    [2, 3],
    [3, 1]
]
people = 3

예상 출력:
expected = False

입력:
std::vector<std::vector<long long>> pairs = {
    {1, 2},
    {2, 3},
    {3, 1}
};
long long people = 3;

예상 출력:
bool expected = false;

입력:
long[][] pairs = new long[][] {
    new long[] {1, 2},
    new long[] {2, 3},
    new long[] {3, 1}
};
long people = 3;

예상 출력:
bool expected = false;

설명

If 1 is on team A, 2 must be on B, and 3 must be on A. The last pair then violates the rule.

예시 2

입력:
pairs = [
    [1, 2],
    [2, 3]
]
people = 4

예상 출력:
expected = True

입력:
std::vector<std::vector<long long>> pairs = {
    {1, 2},
    {2, 3}
};
long long people = 4;

예상 출력:
bool expected = true;

입력:
long[][] pairs = new long[][] {
    new long[] {1, 2},
    new long[] {2, 3}
};
long people = 4;

예상 출력:
bool expected = true;

설명

Put 1 and 3 on team A and 2 on team B. Person 4 can join either team.

접근 방법

먼저 스스로 풀어 본 뒤 힌트를 하나씩 열어 보세요.

힌트 1

이 문제는 모든 제약 컴포넌트를 두 색으로 칠할 수 있을 때만 가능합니다.

힌트 2

각 연결 컴포넌트를 순회하면서 pair 제약마다 팀 배정을 번갈아 주세요.

힌트 3

홀수 사이클 때문에 같은 사람을 두 팀에 동시에 넣어야 하면 답은 false입니다.

예상 복잡도

시간 O(people + pairs), 추가 공간 O(people + pairs)

참고 자료

이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.

CSES: Building Teams