Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
TPCPPLAR - Popular |
English | Vietnamese |
Cho đồ thị G có hướng N đỉnh M cạnh.
Một đỉnh X được gọi là "truy cập" được Y nếu có đường đi từ X đến Y.
Đỉnh X được gọi là phổ biến nếu tất cả các đỉnh Y trong đồ thị thỏa mãn 1 trong 2 điều kiện :
- X truy cập được Y.
- Y truy cập được X.
Yêu cầu : Cho đồ thị G, đếm số lượng đỉnh phổ biến.
Input
- Dòng đầu gồm 2 số N, M (1 ≤ N ≤ 150000; 1 ≤ M ≤ 300000)
- M dòng tiếp theo, mỗi dòng chứa 2 số x và y, thể hiện có cạnh nối từ x đến y.
Output
- Dòng đầu in số lượng đỉnh phổ biến.
- Dòng tiếp theo in chỉ số của các đỉnh phổ biến theo thứ tự tăng dần.
Example
Input: 5 4 1 2 3 2 2 4 4 5 Output: 3 2 4 5
Được gửi lên bởi: | Mew. |
Ngày: | 2014-09-18 |
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: | Tất cả ngoại trừ: ASM64 GOSU PERL6 PYPY RUST SED |
hide comments
2020-08-28 12:27:44
1 đấm AC |
|
2020-08-27 04:13:54
Bài này phải nghĩ thật kĩ, sau khi sắp xếp topo, nếu i là popular node thì tất cả các đỉnh trước i đều là tổ tiên của i => Dựa trên ý tưởng là duy trì số đỉnh có bán bậc ra = 0 trước vị trí i và số đỉnh có bán bậc vào = 0 sau vị trí i (i là vị trí đang xét) https://pastebin.com/isGVT5u9 |
|
2014-10-01 13:43:18 Mew.
Đề bài bị sai, đã được sửa lại :D |