thefacetakt's blog

Searching for Dynamic Connectivity problems
By thefacetakt, 11 years ago, translation, In English

Hello! Can anyone suggest some Dynamic Connectivity offline problems, so i could test my solution?

P.S. Sorry if there was already some topics like this (I didn't find them)

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
11 years ago, # |
  Vote: I like it +3 Vote: I do not like it

http://www.spoj.com/problems/DYNACON1 (I am not sure if it can be solved offlinely) http://www.spoj.com/problems/DYNACON2

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

    Thank you a lot. By the way, it could be solved offline.

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

      how?

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

        Do you want me to tell you algorithm or just say why it is possible to solve it offline?

        → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
        ← Rev. 3   Vote: I like it +16 Vote: I do not like it

        First problem can be solved online using link-cut-tree algo.

        Both problems can be easily solved using sqrt heurisric in , or in per query using the same idea like in segment tree. Both approaches are available in Burunduk1 diploma. But this paper is in Russian. You can use some translation system and understand given pseudocode. Also there are other approaches to solve this problem in the paper.

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

    what is diffrence between this 2 problems?

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

      First one about forest (you are guarantee that after each operation you will have a forest) and another one about graph.

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

Can anyone share their O(n*sqrt(n)) code?

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

https://atcoder.jp/contests/abc301/tasks/abc301_h

→ Reply