Đề bài
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.
Ràng buộc
1 ≤ people ≤ 100,000. 0…200,000 pairs of distinct person IDs in 1…people. Duplicate pairs are allowed and repeat the same constraint.
Ví dụ
Đầu vào:
pairs = [
[1, 2],
[2, 3],
[3, 1]
]
people = 3
Kết quả mong đợi:
expected = FalseĐầu vào:
std::vector<std::vector<long long>> pairs = {
{1, 2},
{2, 3},
{3, 1}
};
long long people = 3;
Kết quả mong đợi:
bool expected = false;Đầu vào:
long[][] pairs = new long[][] {
new long[] {1, 2},
new long[] {2, 3},
new long[] {3, 1}
};
long people = 3;
Kết quả mong đợi:
bool expected = false;Giải thích
If 1 is on team A, 2 must be on B, and 3 must be on A. The last pair then violates the rule.
Đầu vào:
pairs = [
[1, 2],
[2, 3]
]
people = 4
Kết quả mong đợi:
expected = TrueĐầu vào:
std::vector<std::vector<long long>> pairs = {
{1, 2},
{2, 3}
};
long long people = 4;
Kết quả mong đợi:
bool expected = true;Đầu vào:
long[][] pairs = new long[][] {
new long[] {1, 2},
new long[] {2, 3}
};
long people = 4;
Kết quả mong đợi:
bool expected = true;Giải thích
Put 1 and 3 on team A and 2 on team B. Person 4 can join either team.
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
Bài này làm được khi và chỉ khi mọi thành phần ràng buộc đều tô được bằng 2 màu khác nhau.
Gợi ý 2
Duyệt từng thành phần liên thông và luân phiên phân team qua mỗi ràng buộc cặp.
Gợi ý 3
Nếu xuất hiện chu trình lẻ khiến một người phải thuộc cả hai team, kết quả là false.
Độ phức tạp mong đợi
thời gian O(people + pairs), bộ nhớ phụ O(people + pairs)
Tham khảo
Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.