given a directed graph with n nodes and m edges. find all edges that are present in every cycle of the graph
constraints: n<=1000 m<=20000 TL: 0.9s
→ Pay attention
→ Top rated
| # | User | Rating |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3904 |
| 3 | Radewoosh | 3646 |
| 4 | jqdai0815 | 3620 |
| 4 | Benq | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3494 |
| 8 | Um_nik | 3396 |
| 9 | gamegame | 3386 |
| 10 | maroonrk | 3350 |
→ Top contributors
| # | User | Contrib. |
|---|---|---|
| 1 | maomao90 | 164 |
| 1 | cry | 164 |
| 3 | Um_nik | 163 |
| 4 | atcoder_official | 159 |
| 5 | awoo | 158 |
| 6 | adamant | 157 |
| 6 | -is-this-fft- | 157 |
| 8 | nor | 154 |
| 9 | TheScrasse | 153 |
| 9 | Dominater069 | 153 |
→ Find user
→ Recent actions
Codeforces (c) Copyright 2010-2024 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: Oct/22/2024 21:41:09 (i1).
Desktop version, switch to mobile version.
Supported by
Given the low n, we should be considering O(nm) solutions
Find any cycle (if there isn't any then the answer is an empty set). The number of edges in this cycle is not greater than n. Then, for each edge in the cycle, remove it and try to find another cycle. If you don't find one, then that edge was present in every cycle.