【競技プログラミング】AtCoder Beginner Contest 285_D問題

問題

要約

1. N人のユーザがいる。
2. 各ユーザiの現在のユーザ名はS_iで、希望する新しいユーザ名はT_i。
3. S_1からS_Nまでは全て異なり、T_1からT_Nも全て異なる。
4. ユーザ名の変更は1人ずつ行う。
5. 各ユーザは一度だけユーザ名を変更できる。
6. 変更時に他のユーザが使用中のユーザ名に変更することはできない。

全てのユーザが希望通りにユーザ名を変更できるかどうかを判断する問題

既存投稿一覧ページへのリンク

一覧ページ

アプローチ

Union-Findを使用してユーザ名の変更可能性を判断する
（Union-Findで、同一グループに所属する変更を行おうとすると、サイクルが発生してしまうため）

解法手順

1. Union-Findデータ構造を実装する。
2. ユーザ数Nを入力として受け取る。
3. 2N個の要素を持つUnion-Findオブジェクトを作成する（現在のユーザ名と希望するユーザ名の両方を考慮）。
4. ユーザ名を整数インデックスにマッピングするための辞書を作成する。
5. 各ユーザについて以下の処理を行う：
   a. 現在のユーザ名（S_i）と希望するユーザ名（T_i）を入力として受け取る。
   b. S_iとT_iを辞書を使って整数インデックスに変換する。
   c. S_iとT_iが同じグループに属しているかチェックする。
   d. 同じグループに属している場合、変更不可能なのでフラグをFalseにして処理を終了する。
   e. 異なるグループの場合、S_iとT_iを同じグループに統合する。
6. 全てのユーザの処理が終了し、フラグがTrueのままであれば「Yes」を出力し、そうでなければ「No」を出力する。

ACコード

ac.py

# 1. Union-Findデータ構造を実装する
class UnionFind:
    def __init__(self, n):
        # 親ノードのリストを初期化（最初は自分自身が親）
        self.parent = [i for i in range(n)]
        # 木の高さを格納するリストを初期化
        self.height = [0 for _ in range(n)]

    def get_root(self, i):
        # ノードの根を見つける（経路圧縮を行う）
        if self.parent[i] == i:
            return i
        else:
            self.parent[i] = self.get_root(self.parent[i])
            return self.parent[i]
    
    def unite(self, i, j):
        # 二つのノードを統合する
        root_i = self.get_root(i)
        root_j = self.get_root(j)
        if root_i != root_j:
            # 高さが低い方を高い方に繋げる
            if self.height[root_i] < self.height[root_j]:
                self.parent[root_i] = root_j
            else:
                self.parent[root_j] = root_i
                # 高さが同じ場合、統合後の高さを1増やす
                if self.height[root_i] == self.height[root_j]:
                    self.height[root_i] += 1

    def is_in_group(self, i, j):
        # 二つのノードが同じグループに属しているかチェック
        return self.get_root(i) == self.get_root(j)

def solve(n, ab):
    # 3. 2N個の要素を持つUnion-Findオブジェクトを作成する
    uf = UnionFind(n*2)

    # 4. ユーザ名を整数インデックスにマッピングするための辞書を作成する
    user_names = dict()

    # 変更可能かどうかのフラグを初期化
    flg = True

    # ユーザ名のインデックスカウンター
    index = 0

    # 5. 各ユーザについて処理を行う
    for a,b in ab:
        
        # b. S_iとT_iを辞書を使って整数インデックスに変換する
        if a not in user_names:
            user_names[a] = index
            index += 1
        if b not in user_names:
            user_names[b] = index
            index += 1
        node_a = user_names[a]
        node_b = user_names[b]
        
        # c. S_iとT_iが同じグループに属しているかチェックする
        # d. 同じグループに属している場合、変更不可能なのでフラグをFalseにして処理を終了する
        if uf.is_in_group(node_a, node_b):
            flg = False
            break
        else:
            # e. 異なるグループの場合、S_iとT_iを同じグループに統合する
            uf.unite(node_a, node_b)

    # 6. 全てのユーザの処理が終了し、フラグがTrueのままであれば「Yes」を出力し、そうでなければ「No」を出力する
    if flg:
        print("Yes")
    else:
        print("No")

if __name__=="__main__":
    # 2. ユーザ数Nを入力として受け取る
    n = int(input()) 
    ab = []
    for i in range(n):
        # a. 現在のユーザ名（S_i）と希望するユーザ名（T_i）を入力として受け取る
        a, b = input().split()
        ab.append((a,b))
    solve(n, ab)

机上トレース(入力例3)

5. 各ユーザについて処理を行う

2. ユーザ数Nを入力として受け取る

n = 5
ab = [["aaa", "bbb"],["yyy", "zzz"],["ccc", "ddd"],["xxx", "yyy"],["bbb", "ccc"]]

b. S_iとT_iを辞書を使って整数インデックスに変換する

user_names[aaa] = 0
user_names[bbb] = 1

c. S_iとT_iが同じグループに属しているかチェックする

uf.is_in_group(0, 1) = False
uf.unite(0,1) -> 0,1は同一グループ

b. S_iとT_iを辞書を使って整数インデックスに変換する

user_names[yyy] = 2
user_names[zzz] = 3

c. S_iとT_iが同じグループに属しているかチェックする

uf.is_in_group(2, 3) = False
uf.unite(2,3) -> (0,1),(2,3)は同一グループ

b. S_iとT_iを辞書を使って整数インデックスに変換する

user_names[ccc] = 4
user_names[ddd] = 5

c. S_iとT_iが同じグループに属しているかチェックする

uf.is_in_group(4, 5) = False
uf.unite(4,5) -> (0,1),(2,3),(4,5)は同一グループ

b. S_iとT_iを辞書を使って整数インデックスに変換する

user_names[xxx] = 6
user_names[yyy] = 2

c. S_iとT_iが同じグループに属しているかチェックする

uf.is_in_group(6, 2) = False
uf.unite(6,2) -> (0,1),(2,3,6),(4,5)は同一グループ

b. S_iとT_iを辞書を使って整数インデックスに変換する

user_names[bbb] = 1
user_names[ccc] = 4

c. S_iとT_iが同じグループに属しているかチェックする

uf.is_in_group(1, 4) = False
uf.unite(1,4) -> (0,1,4,5),(2,3,6)は同一グループ

6. 全てのユーザの処理が終了し、フラグがTrueのままであれば「Yes」を出力し、そうでなければ「No」を出力する

本入力例では最終的にuf.is_in_group(node_a, node_b)=Falseなので、Yes