Phân nhóm đồ thị hai phía
Points
50
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Cho đồ thị vô hướng gồm $n$ đỉnh và $m$ cạnh. Bạn cần tô màu mỗi đỉnh bằng một trong hai màu (Trắng hoặc Đen) sao cho không có hai đỉnh kề nhau nào cùng màu. Nếu tồn tại cách tô hợp lệ, hãy tìm số lượng đỉnh được tô màu Trắng lớn nhất có thể. Nếu đồ thị không thể tô hai màu, in ra -1.
Dữ liệu vào
- Dòng đầu 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
- Một số nguyên duy nhất là số đỉnh màu Trắng tối đa, hoặc
-1.
Ví dụ
| Input | Output |
|---|---|
| 5 3 1 2 1 3 4 5 |
3 |
Giới hạn
- $1 \le n \le 10^5, 0 \le m \le 2 \cdot 10^5$
Community Discussion