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

Problems Connected Components
Автор phankhai, 10 лет назад, По-английски

I have a large graph (the number of vertices, edges can be in the range of 50,000-100,000). Have 3 queries:

1 .add one adges

  1. remove one adges

  2. 2 vertices x, y belong to one connected component?

Give an answer for each query type 3 ?

Sorry for my bad English.

  • Проголосовать: нравится
  • -7
  • Проголосовать: не нравится

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Google the "Dynamic Connectivity problem"

→ Ответить
»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Tommorow wiil be birhtday of tourist!!!))))

→ Ответить
»
10 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

I read in e-maxx that it can be solved offline using sqrt decomposition.

→ Ответить
»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I think there is a very cool solution with O(N * logQ * logN) complexity but it's offline. The problem is known as Dynamic Connectivity Problem as far as I know, and I'd love to see some efficient not-too-hard to implement solution for the online version :)

→ Ответить
»
10 лет назад, # |
  Проголосовать: нравится -15 Проголосовать: не нравится

Please even once vote up my comment ! I'd be happy.

→ Ответить
»
10 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

You can solve it with a Link-Cut Tree (http://en.wikipedia.org/?title=Link/cut_tree)

→ Ответить