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 |
Given a directed graph G , N vertices and M arcs.
A node X called "accessible" to Y if there is a path from X to Y
A node X called "popular" if every node Y in V fulfil one of two conditions :
1. X is accessible to Y
2. Y is accessible to X
The Problem : Given graph G, count the number of popular node.
Input
- The first line contain N and M, the number of nodes and arcs (1 <= N <= 150000; 1 <= M <= 300000)
- M next lines, each line contains x and y, there is a arcs connect from x to y.
Output
- First line print number of popular nodes.
- Second line print popular nodes in increasing order.
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 |