【AtCoder参加記録】AtCoder Beginner Contest 231【ABC3完】
D問題
https://atcoder.jp/contests/abc231/tasks/abc231_d
に1時間40分ほどかけましたが解けませんでした。
解説を読んだところ、ループする条件がある場合の判定は、Union-FindやBFS, DFSで行えるとのことですが、BFSとDFSについては
アルゴリズム実技検定公式テキスト
https://book.mynavi.jp/ec/products/detail/id=120229
で学習したものの具体的な解法が思いつかなかったため、
アルゴ式のUnion-Findの項
https://algo-method.com/descriptions/132
を読みました。
さらにアルゴ式にはUnion-Findの実装コードがC++とpythonで紹介されており、そちらを用いることで、ようやくACできました。
Union-Find の実装
https://algo-method.com/descriptions/136
ただ注意点として、pythonの実装コードにはいくつか間違いがあるようでしたので修正が必要でした。
具体的には
# union by rank if self.rank[rx] < self.rank[ry]: # ry 側の rank が小さくなるようにする
の部分の不等号がアルゴ式では逆になっていました。
最終的にACとなったコード
# https://algo-method.com/descriptions/136 class UnionFind(): # 初期化 def __init__(self, n): self.par = [-1] * n self.rank = [0] * n self.siz = [1] * n # 根を求める def root(self, x): if self.par[x] == -1: return x # x が根の場合は x を返す else: self.par[x] = self.root(self.par[x]) # 経路圧縮 return self.par[x] # x と y が同じグループに属するか (根が一致するか) def issame(self, x, y): return self.root(x) == self.root(y) # x を含むグループと y を含むグループを併合する def unite(self, x, y): # x 側と y 側の根を取得する rx = self.root(x) ry = self.root(y) if rx == ry: return False # すでに同じグループのときは何もしない # union by rank if self.rank[rx] < self.rank[ry]: # ry 側の rank が小さくなるようにする rx, ry = ry, rx self.par[ry] = rx # ry を rx の子とする if self.rank[rx] == self.rank[ry]: # rx 側の rank を調整する self.rank[rx] += 1 self.siz[rx] += self.siz[ry] # rx 側の siz を調整する return True # x を含む根付き木のサイズを求める def size(self, x): return self.siz[self.root(x)] N, M = map(int, input().split()) uf = UnionFind(N) g = [] for i in range(N): g.append([]) for i in range(M): a, b = map(int, input().split()) a -= 1 b -= 1 g[a].append(b) g[b].append(a) #すでに同じグループなら条件を満たす並べ方は存在しない if uf.issame(a, b): print('No') exit() else: uf.unite(a, b) #隣接する人数が3以上であれば条件を満たす並べ方は存在しない for i in range(N): if len(g[i]) > 2: print('No') exit() print('Yes')