なんとな~くしあわせ?の日記

ClojureとかAWSの設定とかをメモする技術ブログ

AOJ - DSL_1_A を解いてみた



DSL_1_Aは、Coursera Algorithm I で最近習ったばかりのUnion-Findです

AOJ - DSL_1_A

互いに素な集合 Union Find| データ構造ライブラリ | Aizu Online Judge

quick find で求めてみる

自分の回答

時間切れでアウトです

  • 授業でも言われてましたが、quick-findは要素の更新を行う操作がどうしても遅いのです
    id.collect! { |element|
      (element == updated) ? updating : element
    }
lines = $stdin.read
 
array = lines.split("\n")
 
n = array[0].split(" ")[0].to_i
q = array[0].split(" ")[1].to_i
 
it = -1
id = Array.new(n){it+=1}
sn = Array.new(id)
 
for i in 1..q
  com = array[i].split(" ")[0]
  x   = array[i].split(" ")[1].to_i
  y   = array[i].split(" ")[2].to_i
 
  if com == '0'
    updating = if id[x] > id[y]
                 id[x]
               else
                 id[y]
               end
    updated = unless id[x] > id[y]
                id[x]
              else
                id[y]
              end
 
    id.collect! { |element|
      (element == updated) ? updating : element
    }
  else
    #puts "same #{x} #{y}"
    puts id[x] == id[y] ? "1" : "0"
    #puts ""
  end
end

quick-unionで求めてみる

自分の回答

これだと余裕で解けました。

quick-unionのミソは、unionにしてもfindの操作にしてもどちらの場合でも最初に木構造の最上位を求めることだと思われます。(それをしないと、配列上で複数の親をもつ構造が表現できない)

lines = <<'EOS'
10 30
1 3 2
1 0 8
0 6 9
1 1 3
1 8 3
0 6 9
0 7 2
0 0 3
1 2 4
1 1 7
0 4 5
0 4 0
0 4 3
1 0 6
0 1 9
1 5 1
0 4 5
1 0 7
0 3 4
0 0 9
0 6 2
0 3 0
1 9 5
1 9 7
1 7 4
0 9 6
0 3 5
1 6 9
0 2 5
1 8 1
EOS

#lines = $stdin.read

array = lines.split("\n")

n = array[0].split(" ")[0].to_i
q = array[0].split(" ")[1].to_i

it = -1
id = Array.new(n){it+=1}
sn = Array.new(id)

def root(i, id)
  while i != id[i] do
    i = id[i]
  end
  i
end

# find, check if p and q has the same root
def same?(p, q, id)
  root(p, id) == root(q, id)
end

# union, to merge components containing p and q
# set id of p's root to the id of q's root
def unite(p, q, id)
  i = root(p, id)
  j = root(q, id)
  id[i] = j
end

for i in 1..q
  com = array[i].split(" ")[0]
  x   = array[i].split(" ")[1].to_i
  y   = array[i].split(" ")[2].to_i

  if com == '0'
    # unite(4,3) id[4] = 3, 4の頭を3にする
    unite(x, y, id)
  else
    # same
    puts same?(x, y, id) ? "1" : "0"
  end
end

しかしやっぱりRubyは使いやすい