Обсуждение @ 1198. Коррупция @ Timus Online Judge

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

Послано Oracle[Lviv NU] 6 янв 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?

Послано Samsonov Alex [USU] 6 янв 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?

Послано Programmer 11 янв 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?

Послано Programmer 13 янв 2010 00:38

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

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

Послано JTim 7 авг 2010 01:27

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

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

Послано Felix_Mate 10 авг 2015 12:58

Yes! O(1)

Обсуждение задачи 1198. Коррупция