|
|
back to boardSorry, 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 ...... See this:
6 6
1 2
2 3
3 1
4 5
5 6
6 4
The answer is NO But there are no data like this...
I got AC although my program always prints "YES"... is there an algo wich works in O(n+m) for disconnected graphs too? 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. 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. No, I think the answer is
3 4 1 2 6 5 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 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... |
|
|
