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.
I guess, DSU should be solve the problem. In worst case the algorithm would work in O(nlogn).
LE: I thought it's undirected, DSU is useless in this case, sorry
yeah.
Are you sure it's not $$$O(n \log n)$$$? You can't use union-by-rank if the graph is directed.
Can you explain the algorithm? How would you use DSU on a directed graph?
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?
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.
Here is a nice article with $$$O(m^{1/2})$$$ amortized time per edge addition.
Thank you! I'll look at 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.