Tất cả thử thách
Trung bình 1 đã giải Tỷ lệ chấp nhận 100.0%

Can We Split Into Two Teams?

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

Bạn sẽ học được gì

  • Mô hình hóa người và xung đột thành đồ thị
  • Kiểm tra đồ thị hai phía bằng hai màu
  • Xử lý các phần không liên thông của đồ thị

Đề 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ụ

Ví dụ 1
Đầu vào:
people = 3
pairs = [
    [1, 2],
    [2, 3],
    [3, 1]
]

Kết quả mong đợi:
expected = False
Đầu vào:
long long people = 3;
std::vector<std::vector<long long>> pairs = {
    {1, 2},
    {2, 3},
    {3, 1}
};

Kết quả mong đợi:
bool expected = false;
Đầu vào:
long people = 3;
long[][] pairs = new long[][] {
    new long[] {1, 2},
    new long[] {2, 3},
    new long[] {3, 1}
};

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.

Ví dụ 2
Đầu vào:
people = 4
pairs = [
    [1, 2],
    [2, 3]
]

Kết quả mong đợi:
expected = True
Đầu vào:
long long people = 4;
std::vector<std::vector<long long>> pairs = {
    {1, 2},
    {2, 3}
};

Kết quả mong đợi:
bool expected = true;
Đầu vào:
long people = 4;
long[][] pairs = new long[][] {
    new long[] {1, 2},
    new long[] {2, 3}
};

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.

Lời giải đạt tốt nhất của mỗi người. Lời giải nhanh hơn, tốn ít bộ nhớ hơn và được đánh giá cao hơn sẽ đứng trên.

# Người giải Ngôn ngữ Thời gian Bộ nhớ AI đánh giá Lời giải
1 ННикита Python 797 ms - 5/5 Xem code

Học hỏi từ người khác

Giải pháp cộng đồng

Cảnh báo: Có 1 lời giải đầy đủ bên dưới Hãy thử tự giải trước. Bạn vẫn có thể xem mã của người khác và đánh giá AI. Đăng nhập và giải thử thách để tham gia thảo luận.