【Atcoder】Typical Contest 001 問題B Union Findの不正解の理由が分からない

Question

質問内容

AtCoder Typical Contest 001 問題B Union Find（https://atcoder.jp/contests/atc001/tasks/unionfind_a ） に関する質問です．
この問題に対して以下の3パターンのプログラムを提出したところ，以下のような結果になりました．

パターン1：WA（不正解）
https://atcoder.jp/contests/atc001/submissions/74948369

パターン2：AC（正解）
変更点：パターン1の14行目をself.parent[ax] = ayからself.parent[ay] = axに変更
https://atcoder.jp/contests/atc001/submissions/74948437

パターン3：AC（正解）
変更点：パターン1の7行目をself.parent = [-1]*nからself.parent = [i for i in range(n)]，17行目をif self.parent[x] == -1:からif self.parent[x] == x:に変更
https://atcoder.jp/contests/atc001/submissions/74948448

私の理解ではパターン1～3は本質的に違いはないと思われますが，
パターン1だけWAになる理由がどうしても分かりません．ご教授お願い致します．

補足情報

言語：Python(CPython 3.13.7)
不正解のテストケースの内容は非公開

プログラム

# パターン1
import sys
sys.setrecursionlimit(10**7)

class UnionFind:
    def __init__(self, n:int):
        self.parent = [-1]*n

    def union(self, x:int, y:int):
        ax = self.find(x)
        ay = self.find(y)
        if ax == ay:
            return
        self.parent[ax] = ay

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

# 以下共通部分
n,q = (int(a) for a in input().split())
uf = UnionFind(n)
ans = []

for _ in range(q):
    p,a,b = (int(x) for x in input().split())
    if p==0:
        uf.union(a-1,b-1)
    else:
        ans.append(uf.same(a-1,b-1))

for b in ans:
    if b:
        print('Yes')
    else:
        print('No')

# パターン2
import sys
sys.setrecursionlimit(10**7)

class UnionFind:
    def __init__(self, n:int):
        self.parent = [-1]*n

    def union(self, x:int, y:int):
        ax = self.find(x)
        ay = self.find(y)
        if ax == ay:
            return
        self.parent[ay] = ax # 変更点

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

# パターン3
import sys
sys.setrecursionlimit(10**7)

class UnionFind:
    def __init__(self, n:int):
        self.parent = [i for i in range(n)] # 変更点

    def union(self, x:int, y:int):
        ax = self.find(x)
        ay = self.find(y)
        if ax == ay:
            return
        self.parent[ax] = ay

    def find(self, x:int):
        if self.parent[x] == x: # 変更点
            return x
        self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def same(self, x:int, y:int):
        return self.find(x) == self.find(y)

Answer 1

原因は、UnionFindの実装ではなく、共通部分の不具合になります。

問題の「入力」の欄に、​(0≦Ai​,Bi​≦N−1)と書かれていますが、共通部分のコードは、(1≦Ai​,Bi​≦N)を前提として書かれています。

念のため、同じ現象を再現する入力を示しておきます。

2 2
0 1 0
1 1 0

Comments

[catworld]

Pythonのリストは負の値でも参照できることをすっかり忘れていました。ありがとうございます。