Discussion @ 1198. Jobbery @ Timus Online Judge

O(N^2). Is there better solution?

Posted by Oracle[Lviv NU] 6 Jan 2009 02:02

I divided given graph into biconnected components, and then worked with created DAG. This solution is O(N^2) and runs in 0.203 seconds. But there are solutions with better time. Is there faster algo for this problem?
P.S. sorry for bad english((

Re: O(N^2). Is there better solution?

Posted by Samsonov Alex [USU] 6 Jan 2009 22:02

The input in this problem requires O(N^2) time, so the better complexity cannot be achieved :)

Re: O(N^2). Is there better solution?

Posted by Programmer 11 Jan 2010 20:26

Your solution O(N^2*log(N)) in worst case, because the input in this problem requires O(N^2*log(N)) time, so the better complexity than it cannot be achieved.

Re: O(N^2). Is there better solution?

Posted by Programmer 13 Jan 2010 00:38

How to divide graph into connected components in O(N^2)?

Re: O(N^2). Is there better solution?

Posted by JTim 7 Aug 2010 01:27

You can use Tarjan's algorithm to find strongly connected components

Re: O(N^2). Is there better solution?

Posted by Felix_Mate 10 Aug 2015 12:58

Yes! O(1)

Discussion of Problem 1198. Jobbery