tgp07's blog

By tgp07, history, 2 years ago, In English

Let's you have a graph with n nodes and m bi-directional edges. (n, m <= 1e5). How would I get the cycles in this graph in an efficient way using DFS.

BTW, I've linked an image where I drew what I thought is a cycle. If it's not a cycle, please tell me what a cycle actually is.

https://imgur.com/a/Qrrg8DF

Full text and comments »

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

By tgp07, history, 3 years ago, In English

I was working on a problem, and I managed to reduce it to the following question:

Given two arrays of integers a[0], and k[n], perform the following operation n times.

  1. In the ith operation, find the rightmost element in a that is smaller than k[i],

  2. Add k[i] to the right end of a.

  3. Do 1 & 2 n times

I'm trying to use Segment Trees on this, but I'm not able to get the right construction.

Does anyone have a way to do this efficiently(under n^2)?

Full text and comments »

  • Vote: I like it
  • +1
  • Vote: I do not like it