phankhai's blog

Problems Connected Components
By phankhai, 10 years ago, In English

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.

  • Vote: I like it
  • -7
  • Vote: I do not like it

Comments Comments (11)
| Write comment?
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Google the "Dynamic Connectivity problem"

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
10 years ago, # |
  Vote: I like it +11 Vote: I do not like it

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

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 :)

→ Reply
»
10 years ago, # |
  Vote: I like it -15 Vote: I do not like it

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

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply