Discussion @ 1040. Airline Company @ Timus Online Judge

We can construct the answer from the input in O(nm) time ahyangyi_newid 23 Apr 2004 07:31

Sorry, my english is too poor to describe my algo.
But here is a little tips:
For any neighbor positive integers a & b:
GCD(a,b)=1

I.E. GCD(1,2)=1 GCD(2,3)=1 GCD(3,4)=1 GCD(4,5)=1 GCD(5,6)=1 GCD(6,7)=1 GCD(7,8)=1 GCD(8,9)=1 GCD(9,10)=1 ......

Your algo won't work for disconnected graphs(+) Maigo Akisame (maigoakisame@yahoo.com.cn) 28 Oct 2004 15:22

See this:
6 6
1 2
2 3
3 1
4 5
5 6
6 4

The answer is NO

Re: Your algo won't work for disconnected graphs(+) currently unnamed... 25 Oct 2005 17:01

But there are no data like this...
I got AC although my program always prints "YES"...

No subject wefgef 2 Jun 2006 22:16

is there an algo wich works in O(n+m) for disconnected graphs too?

Re: No subject Burunduk1 2 Jun 2006 22:24

I think no.
For exmaple, sometimes answer is NO and strategy 1,2,3,4... doesn't work.
When statements were incorrect (it was not said that graph is connected)
I and some my friends tried to solve it... but we couldn't find
even polynomial solution. So I think no.

Re: No subject GaLL [Tyumen SU] 3 Jun 2006 00:27

If graph is connected ( current statement ), problem can be solved by dividing graph into chains ( like in #1441 ), chains are: k,k+1,...,l . This solution is absolutely correct.

Re: Your algo won't work for disconnected graphs(+) davidsun 12 Aug 2006 07:43

No, I think the answer is
3 4 1 2 6 5

Re: Your algo won't work for disconnected graphs(+) jimdtc 3 Feb 2008 18:30

Sorry,I think your answer is wrong.
See the node 5:the number of one egde is 2,another is 6,gcd(2,6)=2<>1

Re: We can construct the answer from the input in O(nm) time 2-8 2 Feb 2005 17:26

I think we can get the answer in O(n+m)...
Just use the method you mentioned...
Each node has two arcs which numbered x and x+1...

Discussion of Problem 1040. Airline Company