We can construct the answer from the input in O(nm) time

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(+)

See this:

6 6

1 2

2 3

3 1

4 5

5 6

6 4

The answer is NO

Re: We can construct the answer from the input in O(nm) time

Posted by

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...

Re: Your algo won't work for disconnected graphs(+)

But there are no data like this...

I got AC although my program always prints "YES"...

No subject

Posted by

wefgef 2 Jun 2006 22:16

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

Re: No subject

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

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(+)

No, I think the answer is

3 4 1 2 6 5

Re: Your algo won't work for disconnected graphs(+)

Posted by

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