avdp's blog

Help needed in Graph problem [1020B]
By avdp, history, 4 years ago, In English

1020B - Badge

Guys can Someone give me O(N) approach for this problem as When I checked around 20-30 solutions all were O(N^2) so I need a code basically as I have some idea that If a node is in cycle then the answer is the node itself and else the answer is nearest node in a cycle.

Please help me implement code for O(N).

P.S. I checked that no blog exists on this problem and Please forgive me as I know this may be a NOOB doubt and I have started learning Graphs a week back only.

  • Vote: I like it
  • -13
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

why not write a O(N^2) solution, or read the editorial?

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

similar to https://cses.fi/problemset/task/1751

my solution: https://cses.fi/paste/a7027f6882a3d6af144d1a/

edit: Click

→ Reply