A problem with graph

Блог пользователя toilanvd_HSGS

Автор toilanvd_HSGS, 9 лет назад, По-английски

Ok, I will go straight to the problem. Give N vertexes (N<=200000), build a graph by completing M (M<=200000) queries, each of them contain only one integer X (2<= X <= N), that means you must connect vertex 1 to vertex X, vertex 2 to vertex X+1, ..., and vertex N-X+1 to vertex N.

After built that graph, you have to list all connected components of that.

Thanks for your help!

graph

toilanvd_HSGS
9 лет назад
7

Комментарии (7)

Написать комментарий?

ffao

9 лет назад, # |

This code counts the connected components, maybe you can use a similar idea to list them?

→ Ответить

toilanvd_HSGS

9 лет назад, # ^ |

Thanks for your help! This problem is really hard! I still don't understand completely what algorithm is hidden in that source code. I will keep reading.

→ Ответить

ed1d1a8d

9 лет назад, # |

← Rev. 2 →

Notice that if we have a query X, that means vertices with indexes congruent modulo X-1 will be connected. When we process a query, note that it will connect congruence classes. More specifically, if we currently have congruence classes mod A, and we are processing a query B, then we will be left with congruence classes mod gcd(A,B). There is only one slight complication when a congruence class is unable to transition because going left or right would go out of range. We can take care of this problem if we process queries from smallest to largest though. I think the complexity should be NlogN since gcd decreases by at least half each time.

→ Ответить

toilanvd_HSGS

9 лет назад, # ^ |

← Rev. 3 →

Uhm, but in test N= 17, M= 2, X[1]= 10, X[2]= 14, after built edges, there is only congruence class of mod 4, it is not congruence class of mod gcd(10,14)= 2.

→ Ответить

ed1d1a8d

9 лет назад, # ^ |

Yeah you're right, my algorithm above isn't correct. After we process the first query (10), we will have connected components corresponding to congruences mod 9. However, when we process the next query, some vertices will go out of bounds when incremented by 13 (=14-1). For example, if we increment 6 by 13, we get 19, which is out of bounds. In the end of the example above, we will be left with connected components of {1,5},{2,6},{3,7},{4,8},{0} of classes mod 9. I overlooked some things, and the out of bounds problem is actually quite tough to resolve.

→ Ответить