考え方
置換になっている組が存在するとダメなことがわかる.変更前と変更後の名前に辺を貼ったグラフで考えれば,閉路があるということ.
閉路検出 - 競プロはじめました
アライグマ「D問題は、入力例2みたいに、変えたい名前がループしてるユーザたちがいるときだけNoなのだ。ということは、グラフのサイクル検出ができればよくて、DFS/BFSやUnion-Findで解けるのだ!」 pic.twitter.com/l2aQfsizM5
— 競技プログラミングをするフレンズ (@kyopro_friends) January 15, 2023
回答例(UnionFind)
N = int(input()) ST = [list(input().split()) for _ in range(N)] S = [s for s, _ in ST] T = [t for _, t in ST] d = {x:i for i, x in enumerate(list(set(S + T)))} N = len(d) p = [-1] * (N + 1) def root(x): if p[x] < 0: return x p[x] = root(p[x]) return p[x] def unite(x, y): x = root(x) y = root(y) if x == y: return p[x] += p[y] p[y] = x def size(x): x = root(x) return -p[x] for s, t in ST: if root(d[s]) == root(d[t]):exit(print('No')) unite(d[s], d[t]) print('Yes')