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