Tìm khớp và cầu (Cơ bản)
Xem dạng PDF
Gửi bài giải
Điểm:
0,14 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
512M
Input:
stdin
Output:
stdout
Nguồn bài:
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch
Xét đơn đồ thị vô hướng ~G =~ ~(V~, ~E)~ có ~N~ ~(1 \le N \le 10000)~ đỉnh và ~M~ ~(1 \le M \le 50000)~ cạnh. Người ta định nghĩa một đỉnh gọi là khớp nếu như xoá đỉnh đó sẽ làm tăng số thành phần liên thông của đồ thị. Tương tự như vậy, một cạnh được gọi là cầu nếu xoá cạnh đó sẽ làm tăng số thành phần liên thông của đồ thị.
Vấn đề đặt ra là cần phải đếm tất cả các khớp và cầu của đồ thị ~G~.
Input
- Dòng đầu: chứa hai số tự nhiên ~N~, ~M~.
- ~M~ dòng sau mỗi dòng chứa một cặp số ~(u~, ~v)~ ~(u~ khác ~v~, ~1 \le u \le N~, ~1 \le v < N)~ mô tả một cạnh của ~G~.
Output
- Gồm một dòng duy nhất ghi hai số, số thứ nhất là số khớp, số thứ hai là số cầu của ~G~
Sample Input
10 12
1 10
10 2
10 3
2 4
4 5
5 2
3 6
6 7
7 3
7 8
8 9
9 7
Sample Output
4 3
Note
Bình luận
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Nếu bạn bị dính WA 2 test cuối và muốn biết lí do tại sao sai:
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.