ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1198. Jobbery

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)