| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
P134SUMC - SUM4 C - Số thành phần liên thông |
Cho một đồ thị vô hướng gồm n đỉnh đánh số từ 1 tới n và m cạnh đánh số từ 1 tới m. Cạnh thứ i nối giữa hai đỉnh u_i và v_i. Nếu ta xoá đi một đỉnh nào đó của đồ thị, số thành phần liên thông của đồ thị có thể tăng lên. Nhiệm vụ của bạn là với mỗi đỉnh, hãy tính xem nếu ta xoá đỉnh đó đi thì đồ thị mới nhận được có bao nhiêu thành phần liên thông.
Input
Dòng đầu chứa hai số nguyên dương n, m (n <= 20000; m <= 50000).
m dòng tiếp theo, dòng thứ i chứa hai số nguyên dương u_i và v_i.
Output
In ra n dòng, dòng thứ j cho biết số thành phần liên thông của đồ thị nếu ta xóa đi đỉnh j.
Example
Input:
4 3
1 2
2 3
2 4 Output:
1
3
1
1
| Được gửi lên bởi: | adm |
| Ngày: | 2013-07-31 |
| Thời gian chạy: | 1s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
hide comments
|
2020-11-18 09:38:02
code 70đ : https://ideone.com/p2j0YU |
|
|
2014-09-01 17:47:00 Con Bò Huyền Thoại
bài mình sai ở đâu mà chỉ có 70 vậy, @@ DFS+danh sách kề |
|
|
2014-04-09 16:34:02 Hướng Thái Dương
bài hay |
|
|
2014-03-06 16:18:28 Ngô Quang Trọng
tại sao lại 0 điểm là thế nào ? |
