Phân chia hai phe đối lập

Algorithms Buổi 65-66 — Mock HSG Graphs
Points
30
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề bài

Trong một lớp học có $N$ học sinh và $M$ cặp học sinh không thích nhau. Giáo viên muốn chia toàn bộ $N$ học sinh thành hai nhóm sao cho không có hai học sinh nào không thích nhau bị xếp vào cùng một nhóm. Hãy kiểm tra xem có thể thực hiện được việc chia nhóm như vậy hay không.

Dữ liệu vào
  • Dòng đầu tiên chứa hai số nguyên $N$ và $M$.
  • $M$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u, v$ cho biết học sinh $u$ và $v$ không thích nhau.
Dữ liệu ra
  • In ra YES nếu có thể chia thành hai nhóm hợp lệ, ngược lại in ra NO.
Ví dụ
Dữ liệu vào Dữ liệu ra
4 4
1 2
2 3
3 4
4 1
YES
Giới hạn
  • $1 \le N \le 10^5$
  • $0 \le M \le 2 \cdot 10^5$
Draft saved