Phân chia hai phe

Buổi 18 — BFS & DFS
Points
20
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
graph
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. Thầy giáo muốn chia $N$ học sinh vào 2 nhóm sao cho không có cặp học sinh nào không thích nhau nằm cùng một nhóm (tức là kiểm tra xem đồ thị có phải là đồ thị hai phía hay không).

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