Competitive Programing Typical 90 Problem day12

Day 12.

We need the knowlegde of Union Find Tree.

 

Code is below.

H,W = map(int,input().split())
Q = int(input())

class UnionFindTree:
  def __init__(self,H,W):
    self.data = [0] * (H*W)
    self.parent = [i for i in range(H*W)]
    self.rank = [0] * (H*W)
    self.color = [0] * (H*W)
    #色が赤なら1、そうで無ければ0

  def find(self,x):
    if self.parent[x] == x:
      return x
    else:
      self.parent[x] = self.find(self.parent[x])
      return self.parent[x]
  
  def same(self,x,y):
    return self.find(x) == self.find(y)

  def unite(self,x,y):
    x = self.find(x)
    y = self.find(y)
    if x == y:
      return 0
    if self.rank[x] < self.rank[y]:
      self.parent[x] = y
    else:
      self.parent[y] = x
      if self.rank[x] == self.rank[y]:
        self.rank[x] += 1
  
  #ここから問題特異的なコード
  def neighbor(self,r,c):
    node = []
    if H == 1:
      pass
    elif r == 0:
      node.append(r*W + W +c)
    elif r == H-1:
      node.append(r*W - W +c)
    else:
      node.append(r*W + W +c)
      node.append(r*W - W +c)
    if W == 1:
      pass    
    elif c == 0:
      node.append(r*W +c +1)
    elif c == W-1:
      node.append(r*W +c -1)
    else:
      node.append(r*W +c +1)
      node.append(r*W +c -1)
    return node

  def paint(self,r,c):
    self.color[r*W+c] = 1
    neighborhood = self.neighbor(r,c)
    for i in neighborhood:
      if self.color[i] == 1:
        self.unite(r*W+c,i)

UFT = UnionFindTree(H,W)
for j in range(Q):
  inp = list(map(int,input().split()))
  if inp[0] == 1:
    UFT.paint(inp[1]-1,inp[2]-1)  
  else:
    num1 = (inp[1]-1)*W + inp[2]-1
    num2 = (inp[3]-1)*W + inp[4]-1
    answer = UFT.same(num1,num2)
    if UFT.color[num1] == 0:
      print("No")
      continue
    if answer:
      print("Yes")
    else:
      print("No")
  • こちらを参考にしつつ、書いた。
  • 連結判定をするのに、Union Find木が向いている話。
    • グラフ上の2頂点が繋がっているか
      • 地図のある地点Aと地点Bが繋がっているか
      • 人体の組織Aと組織Bが血行動態という観点で繋がっているか
        • 虚血かもしれない
        • 梗塞かもしれない
    • それを高速に判定する
    • 結合、連結状態が変わる場合も、対応出来る
      • 辺を足されても、木を合体させれば良い
    • こちらのスライド。
      • Union Findでは、グループが同じか違うかの判定が使える。
        • ばらばらなグループ分け
          • 素集合データ構造、ともいう 
          • 物を割り当てる
            •  数を割り当て
              • 1組、2組
            • ラベルを割り当て
              • 男、女、職業
          • 構造を割り当てる
            • 木を割り当て
              • これがUnion Find
            • 塊を割り当て
            • 構造の性質を利用
      • 経路圧縮
        • 一回探した子は、直接、根に繋ぐ
      • ランク
        • 木の大きさを考えて繋ぐ
      • 両方で、計算量減らす。