白駿1717号集合の表現

白駿1717号集合の表現

ソース:https://www.acmicpc.net/problem/1717

コード#コード#

import sys

n, m = map(int, sys.stdin.readline().split())
calc = []  
for i in range(m):
  calc.append(list(map(int,sys.stdin.readline().split())))

info_dic = {}
set_dic = {}
now_set = 0

for index in range(m):
  kinds, a, b = calc[index]
  if kinds == 0:    
    if a not in info_dic.keys() and b not in info_dic.keys():
      info_dic[a] = now_set
      info_dic[b] = now_set
      set_dic[now_set] = [a, b]
      now_set += 1
    
    elif a not in info_dic.keys() and b in info_dic.keys():
      info_dic[a] = info_dic[b]
      set_dic[info_dic[b]].append(a)
      
    elif a in info_dic.keys() and b not in info_dic.keys():
      info_dic[b] = info_dic[a]
      set_dic[info_dic[a]].append(b)

    elif info_dic[a] != info_dic[b]:
      li = set_dic.pop(info_dic[b])
      set_dic[info_dic[a]].extend(li)
      for number in li:
        info_dic[number] = info_dic[a]
      
  elif kinds == 1:
    if a in info_dic.keys() and b in info_dic.keys():
      if info_dic[a] == info_dic[b]:
        print('YES')
      else:
        print('NO')
    else:
      if a == b:
        print('YES')
      else:
        print('NO')

解答方法

この問題はPythonのDickShowner資料型で答えました.

info dicで各数値のセットを含むインデックスを保存

set dicで各set dic[index]のセットをリストとして保存

与えられた演算に基づいて条件文で実現

条件は次のとおりです.

a,bが固定集合していない場合

a固定集合がない、b固定集合がある場合

b固定集合がない、a固定集合がある場合

.

両方に固定集合がある場合は、

をマージする必要があります.
この問題自体にはゼロが含まれていて、いろいろな面で間違いを犯す問題条件で、何度も間違っていましたが、解決しました!

Union Find

問題を解決したら、掲示板や資料でユニオンFindメソッドの答えを見つけました!

union

2つの要素からなる集合を1つの集合(並列)に結合

Python文を使用して集計セットを計算するたびに、これらの値のルートノードが変更されます.

find

特定の要素が属する集合が何であるかを示す演算です.

Union情報を含むディックシリーズからルートノードに移動し、要素がどの集合に属するかを知ることができます.

場合によっては、ルートノードは非効率なパスで検索されます.

圧縮パス

は、

を使用して無効なfindを除去し、結合中にノードの情報がルートノードでない場合、ルックアップによってディックシーケンスを再更新する.

ソースコード

import sys

def find_parent(x):  
  if info[x] != x:
    return find_parent(info[x])
  return info[x]

def union(a, b):
  a = find_parent(a)
  b = find_parent(b)
  if a == b:
    return
  elif a < b:
    info[b] = a
  elif a > b:
    info[a] = b

def solve():
  for index in range(m):
    kinds, a, b = map(int, sys.stdin.readline().split())
    if kinds == 0:
      union(a, b)
    elif kinds == 1:
      if find_parent(a) == find_parent(b):
        print("YES")
      else:
        print("NO")

sys.setrecursionlimit(10**5)
n, m = map(int, sys.stdin.readline().split())
info = [i for i in range(n+1)]
solve()