ernestvw's blog

A Graph problem
By ernestvw, history, 5 years ago, In English

Hi. During an algorithm training to prepare the French IOI candidates, we came across a problem, and were wondering about the best complexity to solve it. Here is the statement:

You are given a directed graph with N nodes, that is initially empty. There are M queries that have to be answered online (this is important otherwise the problem is trivial). In each query, an edge is added in the graph, and you have to print whether or not after the edge is added there is a cycle in the graph or not. (Once the first cycle is found, obviously the answer will be yes for all queries after.)

I was hoping that the codeforces community could help us find new and faster solutions to this problem.

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

Comments Comments (10)
| Write comment?
»
5 years ago, # |
  Vote: I like it +9 Vote: I do not like it

I guess, DSU should be solve the problem. In worst case the algorithm would work in O(nlogn).

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it

    LE: I thought it's undirected, DSU is useless in this case, sorry

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      yeah.

      → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Are you sure it's not $$$O(n \log n)$$$? You can't use union-by-rank if the graph is directed.

      → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Can you explain the algorithm? How would you use DSU on a directed graph?

    → Reply
»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Do you have any solutions better than $$$O(m)$$$ per query?

We can get $$$O(\frac{n^{2}}{64})$$$ per query by maintaining transitive closure using bitsets, which is not really better.

Also, are you interested in fast per query solution or fast amortized solution?

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    I am interested in any solution that's faster than O(m^2) and hopefully doable in a contest. Thank you for your help Edit: I hadn't fully read your comment. No, I don't have better than O(m), the intended solution in the training was the one with the bitsets, it was supposed to be an easy problem for the EJOI participants, but we thought there might be some faster solutions.

    → Reply
»
5 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Here is a nice article with $$$O(m^{1/2})$$$ amortized time per edge addition.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Thank you! I'll look at it.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 2   Vote: I like it +5 Vote: I do not like it

      If I remember correctly amortized $$$O(n)$$$ per edge addition can be written during contest (and probably even invented), however $$$O(m^{1/2})$$$ is hard to invent and implement.

      → Reply